Redsnail,
I had a similar problem once with the original Airport base station, so it might not be relevant. I just changed the radio channel the base station was using and it seemed to sort itself out (of course, you have to do this by connecting to the Aiport via ethernet!).
If that doesn't work, it might be worth seeing if there is a worldwide warranty on the base station and taking it to your local AppleStore. It will have a year's warranty in any case. iPods and Laptops have worldwide warranties, but I'm not sure about the Airport Extreme.
AppleMacster.