I also had problems creating a backup of my 60GB in a 40GB external USB HDD. This method worked for me:
1- Deleted all the demos from the PS3 (after all I can reinstall them with the PS3 Proxy)
2- Deleted all the photos, music and movies (they were also already on DVD backups)
3- Formated in FAT32 my 40GB external USB using Windows XP Disk Management (2 partitions: 32GB & 5GB).
4- Used the backup/restore tool of the PS3 to backup basically my purchased games, accounts, game saves, game tools.
5- Installed the new 250GB HDD, formated it for the PS3, formated it again for PS3/Linux, restored the backup, photos, music and movies, and reinstalled the demos.