The program traceroute runs in two modes (ICMP and UDP), by default, it uses UDP. If your NAS only responds to ICMP echo request, you need the -I flag for traceroute.
The * indicates that no reply was received. As your network guys said, a firewall is a likely culprit keeping either the requests from departing, or the replies from coming back. You can at least examine the rules that your firewall is using, I hope, and can perhaps find out whether ICMP messages are passed by the firewall or not.
By default, traceroute chooses which interface to send its packets out by consulting the routing table; this should be correct in nearly all cases. It seems to me that your NAS should be on the same side of the firewall that you are; if not, you should look at the rules determining what packets are allowed between the interface that your computer is attached to and the one the NAS is attached to.