UINavigationController Back Button not visible, but works

Oh Man! Ok, I found the answer in an article on iphonedevsdk.com, now defunct.

It turns out that my first view (the one with the map on it) didn't have a title set (in fact I hide the navigation bar because I didn't want to show it). Even if the title WAS set on a later view the SDK doesn't seem to care. I still don't understand 100% why I could tap in the area to get it to work.

So even though I hide the first navigation bar I still need to set the title of it.

That did it!

Thanks to everyone who tried to help.