No se si sera exactamente esto lo que te pasa, pero te comento, legalmente la nevagacion guiada de google maps no es oficial en europa, google aun esta en negociaciones por lo que si antes tenias instalada una version "no oficial" de google maps, podias tener activada la navegacion guiada, pero si has actulizado desde el market a la 4.1, esa version si es oficial por lo que en europa no hay navegacion guiada....
Ya nos comentas
Saludos!