I've had a look into this, the major problem with the xbox is the limited amount of ram.
Anything that doesn't require a large amount of ram is fine, but from what i've read GPS software are memory hogs, and Navigator which comes as a linux version requires 256mb ram, unlike the 64mb the xbox has.
Actually i was thinking how much resources gps software designed for mobiles would take, like destinator (no linux version though), and get that to work.
You will need to have the xbox modded in some way or another, look here for info.
Since my linux knowledge is very basic, it stopped me from actually implementing this, using it as a media centre