Well I figured it out. First, I was reading the GPS test apps wrong. In both cases satellites showed up in the "radar" display and the number of satellites "in view" changed as I moved around, so I assumed that meant it was getting a signal, but apparently that's not the case.
Turns out the GPS antenna is on corner of the back cover and that corner happened to get particularly beat up when it was run over by who knows how many cars. The contact that is supposed to connect to the antenna on the cover was a little smashed and so was the antenna. To make it worse the cover didn't fit perfectly in that corner either.
So as soon as put a piece of metal on the contact, I got a lock in 5 seconds so it just wasn't making contact with the antenna in the cover. I bent the contact and it works fine now. Sorry for the post.