One of the current YC batch decided to change their name from .me to a .com. You can find their reasoning at: http://blog.imoveyou.com/announcing-our-new-name-getupandmov...
If most of your users are going to find you by putting the company/brand name in google, perhaps good SEO might be enough? I've come across quite a few companies with a .ly domain (can't say how they're doing though).
As a user I probably wouldn't take a .info domain very seriously but .net would be ok.
my 2cents
I once had an email address during college that ended in .at and I'd put it in presentations for classes. People swore I had a typo in my email address. .me, .in., .at, etc. still seem to be a niche sort of thing.
My understanding after this post is that for a web startup, it's absolutely necessary to get a .com. My app, however, is a mobile app first and a web-app second. I'm thinking it's probably OK to go with a non .com address for now. If the app takes off, I'll consider getting a .com. Right now I should spend my time in getting the app off ground. That should be my focus right now.
I definitely would stick with one of the long-time three-letter ones: .org, .com or .net. Nothings says spammer like .biz or .info.
But... when it comes down to it, better to have a 'creative' .com than a .net where the .com is taken.