I think their main problem hiring is that they are looking for perfect candidates. (The same may be true for some of the other DOE labs like LLNL as well.) I've interviewed for at least 3 positions at LANL. I have a security clearance and would love to work for them, but I have never received an offer from them since finishing my PhD. (I did a summer internship with them a long time ago.) Issues like there being relatively few Fortran programmers are convenient scapegoats. They seem to want someone who not only knows Fortran, but also can easily get a security clearance or already has one, can write highly optimized MPI code, is familiar with the unusual numerical methods LANL uses, etc. They seem unwilling to hire people who are 80% of the way there. I've never programmed with MPI, for example, but understand the basics of parallel programming and have programmed shared memory codes. The most recent LANL group I interviewed with also didn't like that I quit a previous postdoc due to disagreements about the direction of the project.
In contrast, in my current job at a DoD contractor, they didn't seem to care much about what I did before or knew previously. They apparently hired me because I had some familiarity with their problem and could learn what I didn't know. I've done well in this job working on things mostly new to me. I'd like to leave because of the bad job security and bad benefits, but otherwise, I have no major problems. (And yes, I do use Fortran on a daily basis here, including some horrendous legacy Fortran.)
Given this, I don't think LANL's hiring problems will stop if they switch all their active softwares to C++ or some other language, because that's only part of the problem.
Edit: Another problem is that LANL's hiring process is convoluted. I almost got an offer from them two years ago, as the group I interviewed with liked me. But they required me to write an internal proposal which would have to be approved by someone outside of the group. I think this is part of LANL's standard post-doc hiring process, though at the time I thought it indicated that they didn't have the money to hire me and were trying to get it. There was no guarantee that the proposal would be approved. I didn't have the time then and backed out, though in retrospect I wish I went through with it as I've heard this is more routine than I thought it was.
Edit 2: Also, for clarity, not every position I applied to required Fortran knowledge. But I think my basic message is correct, in that LANL tends to be fixated on hiring "perfect candidates" when there are plenty of capable people that they could hire instead who just need to learn some things, or might not have a perfect job record (gaps in employment, etc.).