FYI: I ran into this same issue on CentOS 6.5. Old directories had symlinks like:
lrwxrwxrwx. 1 jenkins jenkins 19 Apr 22 09:06 401 -> 2015-04-22_09-06-23

New directories looked like:
drwxr-xr-x. 2 jenkins jenkins 4096 Mar 1 01:28 317

The UI showed the old builds as having run before I was born! In order to re-run the migration I did the following:
sudo find /var/lib/jenkins/ -name legacyIds -delete
sudo service jenkins restart

Once this was done things looked correct.

Integrated in jenkins_main_trunk #3961
JENKINS-26519 Attempting to improve diagnostics in case rename fails. (Revision 4a75e058bafd3cd98832a2a129c9f23c71d26f55)
JENKINS-26519 More diagnostics in case a numeric rename target already exists. (Revision 22dc8add0e106d100a73c16cb628f1c5d1f94538)
[FIXED JENKINS-26519] Build record migration failed on Windows using Java 6. (Revision 7f82ab94a4f6247abaf9f65998360be5c3136bf8)

Result = SUCCESS
jesse glick : 4a75e058bafd3cd98832a2a129c9f23c71d26f55
Files :

• core/src/main/java/jenkins/model/RunIdMigrator.java
• core/src/test/java/jenkins/model/RunIdMigratorTest.java

jesse glick : 22dc8add0e106d100a73c16cb628f1c5d1f94538
Files :

• core/src/main/java/jenkins/model/RunIdMigrator.java

jesse glick : 7f82ab94a4f6247abaf9f65998360be5c3136bf8
Files :

• core/src/test/java/jenkins/model/RunIdMigratorTest.java
• core/src/main/java/jenkins/model/RunIdMigrator.java
• changelog.html

Code changed in jenkins
User: Jesse Glick
Path:
changelog.html
core/src/main/java/jenkins/model/RunIdMigrator.java
core/src/test/java/jenkins/model/RunIdMigratorTest.java
http://jenkins-ci.org/commit/jenkins/7f82ab94a4f6247abaf9f65998360be5c3136bf8
Log:
[FIXED JENKINS-26519] Build record migration failed on Windows using Java 6.
In this environment, Util.createSymlink and .isSymlink are implemented, but resolveSymlink is not.
(cherry picked from commit 388c4b5e6ba52037cae117c5c69f9f4156d41401)

Conflicts:
changelog.html

Compare: https://github.com/jenkinsci/jenkins/compare/1debf06fe6d6...7f82ab94a4f6

Code changed in jenkins
User: Jesse Glick
Path:
core/src/main/java/jenkins/model/RunIdMigrator.java
http://jenkins-ci.org/commit/jenkins/22dc8add0e106d100a73c16cb628f1c5d1f94538
Log:
JENKINS-26519 More diagnostics in case a numeric rename target already exists.
(cherry picked from commit 75c8c31f2fdc98081a0446dd3ee03da7243304a1)

Code changed in jenkins
User: Jesse Glick
Path:
core/src/main/java/jenkins/model/RunIdMigrator.java
core/src/test/java/jenkins/model/RunIdMigratorTest.java
http://jenkins-ci.org/commit/jenkins/4a75e058bafd3cd98832a2a129c9f23c71d26f55
Log:
JENKINS-26519 Attempting to improve diagnostics in case rename fails.
(cherry picked from commit 0633beef0868c59a7e853731aee5f5c0745fa3fc)