Hmm, that's interesting, here in Canada I get my wifi (nome internet) and cellular service from the same company, Bell. If I turn off my wifi I save two or three maybe hops until I am at a main junction point on the Bell network in my province, from my traceroute that looks like
be5.bx01.nycm.ny.aliant.net
that's where my provider (Bell) connects up with a big feed in the US, New York by the look of the name.
If the only difference was the first couple of network hops (how I get to the network point where my Canadian provider joins up with the US provider) then the problem would be with my service provider, Bell. That doesn't seem to make a lot of sense to me as so many others from all over the world on all different carriers are having the same problem as me, they don't use Bell all over the world. It still looks like Apple having the issue on a backend server to me.
I wonder how folks using Macbook Pro running Facetime with an ethernet cable are doing? If they are having troubles too then we can stop looking at how our devices join up to the Internet, wifi, 3g, direct broadband, old dialup modem, the issue will be out on the net and probably down on an Apple resource.