You might have somehow formatted to FAT32 without you knowing it. Anyway if your Time Machine backup is good then try installing the new hard drive and restore from that. Since you are not overwriting your current old drive then leave it alone after upgrading your new hard drive in case you need it.
How do I go about doing that? I don't believe TM backups are bootable... so it would probably involve my OS X install disc?
EDIT: Okay this is bizarre... the disk is now OS X Extended (Journaled)... it magically switched back again!