I had the exact same problem with my eGo 500 MB drive. The drive letter was recognized by the PC but I kept getting the message that it needed to be formatted and was not accessible. The step-by-step from Iomega did nothing to solve the problem. Iomega's data recovery service would have cost $1,500!
I found a utility called Seagate Data Recovery that recognized the drive, its label and all the files on it. It recovered all my files, over 250 GBs! Whew! It was very simple to use. You can download this program free from Seagate and try it in demo mode to see if it will work for your drive. To use it for large files you will have to buy it for $99. Well worth the price!