Hmm, this one is odd. I deleted the old vault and created a new one one the same external drive and it hit the same problem. I used Disk Utility which confirmed there was nothing wrong with the external drive. I then rebuilt the Aperture links using Opt-Alt keys when opening Aperture.
I haven't restored from backup, only because my current library is more up to date and I wouldn't want to lose latest photos etc when its the backup drive that's experiencing problems. I have however created an additional backup drive now on a different external drive and that works fine.
Sounds like it's an issue with the external drive maybe, but Disk Utility can't find any problems. I might just stop using it anyway just to be sure.
All very odd.