When you say you have a CELTA and experience, do you mean you don't have a degree? There is a massive recruitment drive on here at the mo. But I guess you do have a degree if you're going for a masters, right?
The Middle East isn't the goldmine it once was, but you do get well looked after and don't have to worry about rent etc.
If you have a degree, CELTA and experience I'm pretty sure you would find something in the UAE/Gulf.