Usem o tutorial desse site:
http://www.taranfx.com/android-offline-google-maps
Eu segui esse tutorial e fiz o mapa offline para usar junto com o RMaps.
Quanto ao usuário de cima, eu também cheguei a usar o MapDroyd. O diferencial dele é que o sistema de baixar mapas offline é bem mais automatizado, mas pelo menos para a minha cidade o Google Maps é MUITO mais detalhado.
Com relação às funcionalidades, eu achei o RMaps mais prático e completo.
Nesse link que passei, para usar o Mobile Atlas Creator, ele fala que você precisa de um arquivo sqlite_jni.dll. Baixe esse arquivo daqui:
http://sourceforge.net/projects/trekbuddyatlasc/files/
Vá para a pasta Mobile Atlas Creator, depois MOBAC 1.7 e depois SQLite Library.
O tutorial é bem específico e detalhado. Não tem erro.
Agora, quanto a esses certificados que vocês estão falando, admito que não sei nem o que seria isso.
Seria certificado para baixar app da Android Market? Aqui foi de boa para baixar o RMaps.
Meu X10 mini é desbloqueado e sem marcas de operadora, o qual comprei no site do Extra. Não sei se isso influencia.