The asterisks you're seeing are servers that your packets are being routed through whom are timing out (5.0+ seconds) and so traceroute defaults to printing the *.
NOTE: There's even a warning about this in the traceroute man page.
excerpt
In the modern network environment the traditional traceroute methods can not be always applicable, because of widespread use of firewalls. Such firewalls filter the "unlikely" UDP ports, or even ICMP echoes. To solve this, some additional tracerouting methods are implemented (including tcp), see LIST OF AVAILABLE METHODS below. Such methods try to use particular protocol and source/destination port, in order to bypass firewalls (to be seen by firewalls just as a start of allowed type of a network session).
Most firewalls block traffic outbound on ports other than TCP/80 which is the default IP port for web traffic. traceroute in Linux default use UDP, ping use ICMP, so as your output, it seems that ICMP packets are allowed in your firewall whereas UDP packets are blocked by the firewall.
You can see responses to my question titled: traceroute and ping from school network.
EDIT #1
As per the comments, if this is working in another RHEL machine and not working in this RHEL machine, I would suggest doing the below steps.
From the working RHEL machine (machine A), copy the /etc/sysconfig/iptables file. In the faulty RHEL machine (machine B), copy the original /etc/sysconfig/iptables file to something like /etc/sysconfig/iptables.original.
$ cp /etc/sysconfig/iptables /etc/sysconfig/iptables.original
This step is just to ensure that if something goes wrong with our setting, we can revert back to the original. Now, copy the /etc/sysconfig/iptables from the machine A to machine B.