From the router to your computer there will be at least one switch and there might be a problem on the switch (or on your computer). Ask your provider to plug your server on different switch port or different switch and see if that helps.
I must say this is a poor method of troubleshooting. Its best to work your way out in this type of problem. Rule out any operating system problems or filtering of traceroutes (some OS'es have thresholds for how much ICMP they'll allow, it could just be a coincidence that the ICMP threshold has been hit). Contacting the ISP is probably a good idea aswell, after ruling out any problems you have on the machine itself (assuming is a dedicated server, not shared). Switching switchports may be a waste of time at this point in the game.