I've been researching throughout this issue. One of the coolest features I basically fell in love with my previous iPhone 3G, is the fact that I could use GPS without having a data plan, or a WiFi network available. However, due to the limitations while unlocking a 3Gs using an iPad baseband (6.15.00), the GPS seemed to be affected, and push notifications as well. There might be a solution for this though...
I remember I had a Microsoft SideWinder Steering Wheel, which took about 5 minutes to be detected by the Plug and Play feature in Windows. No matter what computer I used, it took that amount of time for some reason. A friend of mine had the same model, and was immediately detected.
This helped me ten years ago to determine that hardware is sometimes not as faithful as a designer probably thinks it is. If we analyze the situation, there are several factors that may cause hardware to not work appropriately.
After the 4.2.1. jailbreak using Pwnage 4.2, I figured out notifications were not arriving still. At least it didn't while recently jail broken. I uninstalled the TomTom GPS application I purchased earlier for my 3G, dying to all expectative of seeing it work.
As soon as I removed TomTom, I figured out I started receiving notifications from Facebook, Messenger, and everything else. TomTom released an upgrade recently, from 1.5 to 1.6. Maybe not recently, but I was just able to obtain it today.
At first, I noticed nothing different from the previous version. GPS was on, but "waiting for GPS signal". Nothing changed. Until I was driving to work, where I figured out the map was somehow using a weak signal, but managing to keep me on track (see below).
Please note I don't have a data plan or WiFi connection. When I finally arrived, I kept playing with it until I saw it successfully tracked my location and gave me a route to a recent address I was trying to navigate.
Apparently, GPS is not dead. Reception is weak, or what I totally assume is that software somehow, is preventing you to use it. If you have a data plan, or you are connected to a WiFi network, GPS will work perfect, and will track you no matter which app you're using (Google Maps, TomTom, NDrive, etc).