Possible reason is that something is mangling the packets ie. if packet size mismatches then you receive such errors. Also, another reason is that default packet size is not sufficient enough then too it gives this error. However, it is also most possible reason in your case as you do not get above error if you ping first. And reason might be that when you PING first, system automatically determines required ICMP packet size for that particular host hence you do not get error afterwards.
However, reading elsewhere on web, it was found to be a bug in traceroute with CentOS4.x , since centOS is derived from RHEL, so same might goes with RHEL too. You may try to get most recent traceroute binary and see if it is solved.
