You are absolutely correct, ktrack, 4800 baud and NMEA compliant, which covers most of GPS receivers on the market these days. These units are inexpensive, and I'd go very likely with a simple USB GPS receiver such as Globalsat BU-353. It has SiRFstarIII chipset,so you get very good performance.
However, before you spend your hard earned money, there is still a slight chance your existing GPS receiver is good. Sometimes it just takes much longer for a GPS receiver to start working for the very first time. Connect it to your laptop, bring it outdoor so it can see the sky in all directions, and then let it just sit there for 30 minutes. After 30 minutes start you Streets & Trips to test it.