I'm 5'11' with a 32' inseam. I ride a 56cm. Might want to rethink...
Pretty tough to buy something online without knowing what you should be looking for.
Try walking in to a local bike shop and tell them what you want including your budget etc. They'll probably show you a couple and tell you what size you should be looking at. Maybe you take that info and buy something online (bikesdirect.com or similar) but I'd talk to a 'dealer' for a little while before jumping at something shiny online
If you want a good bike, I think it is worth the premium you'd pay to buy from your local bike shop. (LBS)
I just bought a Gary Fisher Simple City 3 from a local shop. Not only did they assemble it, but they helped me choose it and fitted all the accessories I bought too. It is good to keep these local places in business. The prices were higher, but they were so happy for the business that they discounted all the accessories and even threw in a couple of the smaller ones for free. (tire levers, spare inner tube)
If your local place is a long drive (or ride) call them first to try to get an idea if they'll have what you want.
I did buy my second most recent bike online; from a bike shop in New York City. There was a manufacturing defect in which the front wheel wasn't even. It is just a little thicker near the seam, so that when I brake, it is uneven and noisy. In order to get it resolved, I'd have to repack and send the WHOLE bike back to them, at my cost.
The moral is that if you buy locally, it may cost a bit more, but you know what you're getting, and you'll get batter after-sale support. If you buy online, you may not know exactly what you're getting (ex. how it fits you) and after-sale support will be difficult and/or expensive.
I would even go as far as to recommend a slightly lesser bike if money is that much of an issue, just so that you can buy locally.
Added note: When you get to be a heck of a good bike mechanic and you know which components fit which bikes and all about different sizes, then you no longer need the service of your LBS and you can look for deals on fleabay.
thanks for all the help guys, I think I'll definitely have to go look at the LBS again and see whats up and to get better measurements and fittings. Tober1 - yeah, I did get caught by the shiny thing haha.