Bluetooth would be great, yes. Making an Arduino and an Android communicate with BT is pretty easy. You can get really chez BT chips on eBay that works like a charm (I do that for my project).
Then you need to know exactly what kind of data you could get from the Android and how it is formated (JSON, XML, raw coordinates, something else?).
Do you know if you can get the data from directly from the Google Maps App on the phone?
What I would do (if it's possible, I'm not sure): rebuild some kind of GPS application which sends "markers" to the Arduino via bluetooth, i.e. when you're less than 100 meters away, it tells the Arduino to blink faster, if you took the wrong exit, it starts recalculating and tells the Arduino to blink red, something like that.
Is that what you intend to do? Or am I totally wrong? :)