Han sa også at det fortsatt gjenstår å få kontakt med flere fjerne kystområder, som kan være særlig hardt rammet av flodbølgene etter skjelvet.
-Vi har ennå ikke oversikt, men jeg anslår at mellom 21.000 og 25.000 mennesker kan være døde.
Det sa Yusuf Kalla etter at han kom tilbake til Sumatra etter et besøk i Banda Aceh.
Rapporter fra Acehs sørvestlige kyst forteller om enorme ødeleggelser i et område der det bor nærmere en million mennesker.
Det offisielle dødstallet fra Indonesia er 5700.
14.000 døde på Sri Lanka?
Samtidig sier myndighetene på Sri Lanka at 14.000 mennesker kan ha mistet livet da flodbølgene traff øya og at 2000 av dem kan befinne seg i områder som blir kontrollert av opprørere.
Til nå er det blitt registrert flest døde på Sri Lanka, og i dag melder UNICEF at også landminer utgjør en fare for de overlevende og for redningsmannskapene.
Minene ble vasket vekk fra merkede områder av flombølgene, og varselskilt er også blitt ødelagt, sier lederen for FN-organet i Colombo.
Den største faren er for sivile kommer når de vender tilbake til hjemmene sine, mener han.
Kvinne på Sri Lanka leter etter sin sønn /Scanpix/AFP)
Landminene har vært brukt på øya siden konflikten mellom regjeringen og de Tamilske tigrene startet i 1972.
Et tog som ble tatt av flodbølgen, hadde rundt 1500 passasjerer, opplyste myndighetene i dag. Alle ble tatt av vannmassene og døde.
- 700 utlendinger døde i Thailand
Samtidig sier viseinnenriksministeren i Thailand at over 700 utlendinger kan ha mistet livet da flodbølgene rammet landet.
I går sa FN at opptil 60.000 mennesker totalt kan ha omkommet og at katastrofen er en av de verste som verden har sett.
Det norske utenriksdepartementet opplyser at 13 nordmenn er bekreftet omkommet og at mellom 20 og 40 er savnet.
29.030 registrert omkommet
Tirsdag morgen oppjusterte nyhetsbyrået Reuters tallet på registrerte omkomne til 29.030.
Av disse var 12.212 registrert på Sri Lanka, 9499 i India, 5700 i Indonesia og 1473 i Thailand. Også på Maldivene og i Malaysia, Burma, Somalia og Bangladesh var det registrert døde.
Tallet inkluderer rundt 5000 døde å de indiske øyene Andaman og Nicobar.
Opplysninger fra landene som er rammet, tyder på at tallet på omkomne i landene kan stige til nærmere 60.000.
Hjemløse i India sørger over sine døde (Scanpix/AP)
Lyd og video
- Det viktigste er å hindre at flere omkommer, sier Jan Egeland, koordinator for FNs krisehjelp
- HØR: Kaos i Phuket. Rapport fra NRKs reporter Philip Lote
- HØR: NRKs reporter Knut Magnus Berge sier minene vil utgjøre en ny fare på Sri Lanka
- HØR: NRKs reporter Geir Rommetveit om situasjonen for turistene på Sri Lanka
- VIDEO: Bølgen treffer Phuket
- Video: Sonia Gandhi har besøkt Andaman-øyene
- VIDEO: Svensker og nordmenn hjem