If you are on Verizon's California network, I have not been able to do successful traceroutes past the verizon/bbnplanet to Level3 router for over a month now. I get four hops and it dies.
I've talked to other Verizon customers in the Verizon newsgroup's and this seems to be common. Although Verizon support has disavowed any knowledge of it, common guess seems to be that Verizon is filtering ICMP packets at their borders, causing most traceroutes to fail. Mine consistently go four hops and die.
If you can traceroute with some other kind of packet, such as UDP or SYN you may have different results.
Anyhow, not sure if this is what your problem is, but thought that it *may* be, so thought I'd share my frustration. I spent many, many hours on hold to come to this conclusion.