I have to admit I didn't "Safetly Eject", but I have done this a million times... what gives, and how do I get my data back??
Ubuntu doesn't "randomly format" drives, so you could make your question a bit less dramatic...
Unplugging a device with a file system on it without unmounting it is guaranteed to cause problems sooner or later, and if you are using a FAT filesystem on it, it won't easily "repair" itself like ext4 or NTFS would. But we don't know what the exact cause of your problem is in this case.
It might be useful to look in your log files (dmesg, syslog, etc.) to see if there are any error messages when you plug in the USB memory stick.
If there are no read errors, it's probably "only" the filesystem that got corrupted. You can use a simple
In case there are hardware problems, or a simple fsck doesn't solve the problem, you can try using tools like photorec on a disk image (which can recover not only graphics files but also a lot of other document formats).
Building on what aking said:
First things first, get a bit-for-bit copy of your USB key that you can work on. Working on the USB key directly will likely make things worse.
To make the copy insert the key and note what device it appears as in dmesg (it will be something like /dev/sd[bcdefg...]). You can then copy the whole image using dd:
You can then poke the image file with various recovery tools to see if you can get the data off. I would install "testdisk" and use that to see if the data is recoverable.
The testdisk package comes with a specialised tool called photorec which is geared towards finding pictures. It has a fairly good success rate even if the filesystem structure is pretty hosed. It relies on the fact that most lightly used memory devices store file in sequential blocks.
However whatever you do don't try playing directly with the USB save for making the first copy of the data.
Some good resources on recovering data:
There are also several live distributions that specialise in forensics and data recovery. SystemRescueCD is but one. In your case, you probably won't need it since it is just a usb key, but if it was a hard drive then you might want to keep a copy handy.
Best of luck!