TomTom use "TeleAtlas" maps, and in fact they actually bought TeleAtlas several years ago.
As with most mapping companies, TeleAtlas has varying levels of coverage for different countries. For countries like the US, TeleAtlas has near 100% coverage, which is to say that they have not just major highways, but all the way down to minor streets and even (in some cases) dirt roads and the like.
For some countries, they only have "major road" support, so they have highways and some major metropolitan roads, but little else. These countries include places like Mexico and South American countries, and much of Central/Eastern Europe.
Iceland has always been a strange case, in that TeleAtlas have never had any coverage of it. I can only presume this is a business decision in that they have decided it's not worth the money/effort to create such maps, and I'm not aware that any official reason has been given.
Other GPS manufacturers use different maps. eg, Garmin use maps from Navteq in much of the world, and Navteq do have maps for Iceland - thus so does Garmin.
Currently there is no way to load maps from any other sources onto TomTom devices, so your only option is to either buy/rent another brand such as Garmin, use a paper map (remember them?), or perhaps just get lost (which can often be lots of fun!)