What happens if (for others, since I see you are not using an iPhone so can not make a voice cell call) you make a cell call first, then enable/reqeust facetime? I find that if I make a facetime call, both sides see the dreaded "connecting...." until it gives up. But if I make a cell call first, then switch over it works better. It still was giving "poor connection", despite both ends having excellent conectivity. I think in both cases it will end up using wifi despite the 2nd method starting on cellular.
it is most annoying and is something I did not experience prior to IOS 6 (both ends are running 6.1.2)