I just started using the service a couple of days ago, and I'm very impressed. Awesome work.
I can understand your problem, though. Honestly, I'm not sure that I would pay anything for it, but I'm not a business user or anything - I'm just using it as a slight convenience.
So, for me at least, there's not much value. Maybe I'd pay a one-time fee for some kind of convenience, or to stop ads. I payed $10 for the Instapaper iPhone app, but mostly as a "thanks for the awesome service" kind of thing. I could see doing something similar for this.
Having some kind of ads doesn't seem like a bad idea, and maybe they could be coupons or something? I dunno - maybe something where you got an affiliate deal? I'm not sure how much I would tolerate, but if it was good stuff, maybe a couple a week.
I'm just a joe-average-user guy, though, so I'm not sure how valuable I would be as a way to profit. If there's a way to get after business or heavy users, that might be the trick.
If it's not very expensive to run, perhaps you could open-source it or simply use it as a portfolio piece. I've done some open-source work that ended up benefiting me when I was looking for work. At the very least, that should be somewhat valuable.
Sorry I can't be much more help than that. I think it's a great little utility, but maybe this is a "feature not a product" situation. Perhaps you could try to sell it to Twitter directly...? License it to UPS for exclusive use...?