Hi,
Yes, I am busy upgrading Backup Exec 11D straight to 12.5, and it has sorted out some of my issues on sites, while opening up issues on others! But the upgrade is possible. Just make sure you leave the option to backup your data. If you don't, you have to recreate all your jobs, media sets etc.
Are you perhaps not filtering your restore list? Take it back to a date a couple of months before you want to restore from.
Don't forget to catalog your media first...if it's old, and your catalogs have expired, they won't show up.
Laters!