I had a similar problem just this past weekend and here is how I recovered 3 lost videos from my Galaxy S android phone.
1) Use the USB cable supplied with your phone and patch it in to your pc. It should be recognized as a drive (H: for mine).
2) Download and install EASEUS Data Recovery Wizard Free Edition 5.0.1 from Free Data Recovery Software to free recover deleted files and recover formatted or corrupt hard drives - EASEUS Data Recovery Wizard Free Edition.
TO YOUR PC.
3) Start the application and point it toward drive H: (will be different for you I'm sure)
4) Check off the types of files you want to recover. I deselected music files as that would put me over the 1 gig limit that the free version of this software will recover. I did not specifically choose sub-directories as the software handles this just fine.
5) Let it run. It took the software about 1 hour to recover 105 deleted files
(you must choose where to save the files, somewhere on your PC, I created a special folder called c:\recovery just for this).
6) After it is done, Browse the files in your recovery folder, keep what you need and delete the rest.
Important: Do not save ANYTHING to your phones drive when you realize you have deleted something important. Turn off wi-fi, email alerts, facebook, etc. I would suggest turning your phone off immediately to prevent this until you are ready to recover files.
Good Luck, it worked fine for me.