I don't know how the BBC restricts the feeds by geography but its possible that they have a list of 'good' IP addresses.
Each ISP has a unique IP seed (XXX.XXX) and its just possible that if you're not using a 'common' ISP that they are not on the list so the BEEB assumes you not in the UK.
Check a friend who has the same ISP as you!
The BBC has used this ISP restriction method on some of its Broadband TV trials so its reasonable to assume that they could use it on Audio.
The symptons you mention are almost identical to reality for us expats.
Except that I do get the 5 Live international feed when they are no copyright restrictions
Try a IP locator such as http://www.ip-adress.com/
to find out where the BBC thinks you are!