Also, we ran into the surprise of discovering our potential userbase: the 12-18 crowd stormed in like bulls in a china shop posting sexually explicit pictures, profanity, etc. which created a whole new slew of headaches. It's a valuable/lucrative audience, but you need a fair amount of policework to prevent things from getting out of control...
One of the fellows at SmugMug has blogged about the "free" question, and pointed out this particular problem with "free". When it's free, you capture a part of the market that most wants anonymity and no recourse for their bad, possibly illegal, behavior. 12-18 year olds exchanging sexually explicit pictures via your service is a problem of epic proportions. Stopping it could very easily become your full-time job (and the full-time job of a dozen more people).
I know you've said you've already halted free distribution. I just wanted to point out that this one is a well-known problem with free, and if you don't have good, automated, methods for dealing with it, it can be a huge resource drain.
Market validation is once you have the data to say "customers in demographic X will pay Y dollars for this app, I will make a margin of Z percent, and there Q customers willing to pay."
Unless you can survive on your free version (which it sounds like you can't), you haven't validated the market yet. Find the price point where you are profitable (and people will pay!)
It sounds like going the free route was a mistake. Bootstrapped startups have to charge something to somebody, and you-pay-me-for-my-product is a time tested way of doing it.
As for the rest, you need to tamp down your costs. $30/day is extremely high for a bootstrapped, no-revenue startup. Find a way to cut this down. Based on your comments about GAE and SQS, see about moving to a standalone VPS (Slicehost or whatever) and running your own ActiveMQ server, probably on the same machine. It's hard for me to imagine a web app w/ less than 10k users needing more than a single big VPS.