Be upfront. Tell them its not supportable and negotiate what is. If they enjoy your service so much they'll be wise not to kill it through overuse, and it might be that they have the means to make your needs seem less worrisome.

If not, they're jerks, and you can feel better about changing the terms of the deal. Do the full Darth Vader routine on them. Act like you are AT&T.

Having an unlimited plan is a great way to attract a small group of users, but it can backfire (as you're discovering). What percentage of your users are on the unlimited plan? As other posters suggested, you might consider replacing the unlimited plan with something more sustainable and less open to abuse (for lack of a better word). You'll have to weigh that against the revenue that you risk losing by alienating some of those power users. But if it's only some users, you might be able to afford losing some or all of them.

This is a common rite of passage for early-stage startups :)

The answer may sound glib but I don't mean it as such: don't have an unlimited plan and migrate existing customers off it.

It sounds like your unlimited plan is not actually unlimited. You could take a page from telecom and "throttle" the app for users over certain usage thresholds. Put their requests in a queue, etc

If you can't handle unlimited then don't offer unlimited? Really just is that simple.