I have a 8130 from US Cellular. I also have Garmin installed and working. There was no tricks, after install it just worked. It does take 1-2 minutes for a lock. If I think it is taking to long I usually will kick the GPS in the pants by launching GPSed. That little app will always get things going. There has been an occasion or two when a reboot needs to take place. Have not figured out which app causes this issue.
For testing I would start out with GPSed the move to BBMaps and then Garmin.