Ok, I accept a little bit of the blame for this one. I started to import my photos using picasa. The first three pictures that were imported were poor, so I decided to delete them. At that point they were the only pictures in the folder, so Picasa decided to delete the folder, even though an import was going on to that folder. All the rest of the pictures went into the abyss. Pretty lame IMHO. Picasa should probably check that it's copying the files to a good location before deleting them from the card.
Luckily someone was nice enough to write an easy undelete, testdisk has a nice utility called photorec. I started up photorec with the device of my media card and it found all the deleted photos (486 vacation pics).
[root@imanidiot ~]# photorec /d Recovered /dev/sdb
Photorec has a nice curses menu that was easy to understand and it recovered my files fast. They have versions for linux, windows and dos and that other annoying thing with an X in it.
Thanks a lot CGSecurity.