Nie wiem, jaki masz tam system, ale dla ICS:
Menu => więcej => sieci komórkowe => Centrum SMS
Dla Gingerbreada i wcześniejszych będzie to chyba:
Menu => połączenia => sieci komórkowe => Centrum SMS
Generalnie nie powinno się odinstalowywać takich aplikacji systemowych. Receptą może być zrobienie wipe, ewentualnie zainstalowanie samej aplikacji poprzez wrzucenie jej do system/app (bo skoro usunąłeś, to musisz mieć roota).