I figured out what it was - Yes it is a VSS and there are no gear assembly pieces for the MTX. However I learned some important things:
1) There are 2 VSSs for the 2003 Protege. There is one is for the Automatic transmission and one for Manual.
Part number for the Automatic is SU6385 and looks like this:
Part number for the MTX sensor is SU6386 and looks like this (notice the blue gear, that's one of the main differences as well as the placement of the bolt)
2) To remove this, you will need to take out the following (note that EVERYTHING takes a 10mm socket which is awesome. I suggest 2 or 3 long extensions though):
Battery harness (the entire thing, even the part the battery sits on)
Air intake hose, just remove the whole thing. You can keep the filter box in, just take the top off.
Standing at the driver's side wheel, look down near the back of the tranny. You should see a bracket making a U shape (or a backwards C shape if you're looking from the front) with two bolts. The bracket goes around the sensor, you should be able to see the electrical connector going into it. It's straight up and down. Remove the two bolts and the bracket, otherwise you won't be able to get the damn sensor out and you'll just get angry.
Remove the 10mm bolt near the sensor after removing the electrical connector. The connector can be a little tricky to get out. After removing the bolt, grip the sensor as well as you can and turn it back and forth a bit to loosen it while pulling up. Eventually it should pop out. Put in the new sensor and put everything back together. Tada!