Turns out that I can make call to our iPad just fine if I'm on wifi.. Just can't call it when I'm on 3G/LTE. The other end rings but when answered both ends get stuck on "connecting".
After upgrading both devices to 7.1.2 just to be sure I did a bit more digging. I've found it actually works fine if I switch my mobile to the "direct" APN. Guessing something about the inbound ports required for FaceTime is causing grief.
I'm now thinking the 3G calls that randomly seemed to work when I was out of town were probably when I was roaming onto Vodafone.
If any 2d guys spot this, is there any chance we can get FaceTime working properly on the "internet" APN? After all, you are an official Apple retailer now :)