"What's weird is that I am constantly getting 6-10 satellites, but SD and S&T won't 'lock.'"
6 to 10 satellites should be enough. The u-Blox5 based unit included in S&T09 is a usable unit. The chipset has a slightly better sensitivity than SiRFstarIII, but the antenna is smaller, so the over all performance is slightly worse than for example BU-353. But it is usable. I have been using it with no issue for at least a couple of months now (on a daily bases).
Here's a brief review: u-Blox 5 USB GPS Stick - New GPS 'Locator' for Microsoft Streets and Trips
The GPS receiver is not really made by u-Blox. Only the chipset is by u-Blox. The unit is made by company named Navation Technology, and the product name is Navation GPS 168 (it is on the sticker on the back of the unit). I'm not sure if it is a good idea to download a firmware from u-Blox site. Instead, you may want to check if there is a driver update available on Navation's site. But I'm not sure if that will solve your issue, which may or may not be related to the USB GPS receiver at all.
Have you tested your set up with another USB GPS receiver? If not, could you? Or could you test the GPS unit on another PC?
Streets and Trips