Yes, location is on. My friend also had an XV6800 and got a new one and has the EXACT same issue. The only difference I can see is this, not sure if it matters:
New Phone
PRL Version: 51433
PRI Version: 2.03_002
Old Phone
PRL Version: 51345
PRI Version: 1.35_002