If you use a DOS prompt (command.com, not cmd.exe) and list the files, do you see AUTOEXEC.BIN?
Or, in cmd.exe, try dir /x (it should show AUTOEXEC.BIN, but it should not show long file names).
Does the camera boot when the card is bootable?
Yes, there is difference if you format the card on PC. Maybe cluster size or other stuff like that could make a difference (even creating a smaller partition is worth trying).