The G in GFCI causes a lot of confusion. A ground fault does not necessarily involve the ground wire. In fact, if it only involved the ground wire then it would trip the breaker and there would be no big need for the GFCI device. However, a ground fault can send current to the literal ground through a person, and that is where GFCI protection becomes critical, particularly in areas with water (kitchens and bathrooms).
The internal test of a GFCI (the "TEST" button) does not require a ground wire to operate, so that works fine. Which is good!
The typical plug-in GFCI tester works by sending a calibrated amount of current from the hot wire to the ground wire. If the ground wire is not connected then that current can't flow - and the test button has no effect. So your current situation (GFCI test button works, plug-in test doesn't work, ground wire appears to not be connected) all matches 100%.
In certain situations, GFCI can be added where GFCI is not required instead of retrofitting a ground wire. That does not apply to your situation because you have a ground wire in place - it is just broken somewhere and needs to be fixed.
The most likely locations are:
- The first place where it doesn't work - but you've already replace the outlet, etc.
- The last place where it does work. Normally that will be another receptacle. It is also possible to have a junction box between receptacles, so look for that as well.
I will assume for the moment that you don't have metal conduit (because that acts as a very effective ground unless something is really messed up) or any conduit at all (since most places in the US use NM (a.k.a. Romex) cable). If you have metal boxes, the ground wire should go to the metal box as well as to any devices. Properly installed, most devices (all switches, better quality receptacles including GFCI/receptacles) should ground automagically to metal boxes. If you have plastic boxes then you need to make sure ground wires go to the devices correctly. In particular, if you have a device that acts as part of a daisy-chain then you should pigtail the ground wires (in + out + pigtail to device) because normally you can't (reliably and according to code) put two ground wires under one receptacle screw.