I downloaded the GPX to shapefile tool and when I use it I get the following error message: 1 No module named re Failed to execute (gpx2shp).
The script is failing to find the Python regular expression library, which is strange because re is part of core python.
You could open the Python console in ArcMap, and
import re to see if the same error occurs.
As @artwork21 suggests, you could browse to your python installation and see if re.py exists.
You could start python from the command line and see what version is reported being installed (though re has been part of python since 1.6 or so). I'm not familiar with the tool you're using, but maybe you'll discover that python isn't in your path and this tool requires it?
Adding python to path
Follow the instructions here. On step 4, enter
;C:\python26\ArcGIS10.0 (be sure to verify this. Will be the same path you followed to run python in one of your comments)
If, after logging out and back in, you can type python at a command prompt and it works, I'll bet this tool will run as well.