Well it's working again. I have tried this a few times with no luck but this time is fine. Uninstalled K9 and used the standard email program for a few hours and I was getting notified, downloaded the K9 version from the market and all is fine. I'll try turning on WiFi today as well.