Theoretically we don't have to launch in the UK but the total budget for the first balloon is £1k so realistically we're limited to the local area. For similar reasons I don't think setting up a dedicated mobile phone transmission tower is a practical possibility... certainly much less feasible than persuading Ofcomm to let us fly a ham transceiver. We're more than willing to get ham licenses but even with one you're not allowed "any unmanned stations". We're looking at going down the commercial license route for later ballons but I think that involves real money and real hassle.
Whopity, not sure what you mean about using an FCC license? That would be difficult to get and almost certainly not valid here. Or are you joking about flying on an FAA PPC :P
Yeah we are looking into PMR, 40 miles or so (the range we'd like) might be pushing it even with line-of-sight but worth a try.
Jamydonut, unfortunately an Iridium phone costs about £800 which is 80% of the total budget... but that is probably what we'll use for later balloons which may be aloft for weeks at a time and will go a long way from home.
IO540, I'd love to stick an industrial radio modem on it but I can't find any license-free ones which offer that sort of range, even in free air. They all seem to be limited to 100mW.