Did you deleted /var/lib/gps/nvd_data before restarting? If you did, then it seems a hardware problem. Is it still under warranty?...