Iceland is known for its horizontal rain (i.e. rainfall combined with 50+mph wind). Add long days in the summer and long days in the winter. Add no trees at all. It's a somewhat extreme place.
When I dropped into street view of an Icelandic suburb I was surprised how many trees I saw. Maybe it's an issue of topsoil rather than climate?
Yes, from I've read it's definitely the issue of soil. The island was completely deforested a long time ago and the unprotected soil has completely eroded since then (the same thing also happened in Scotland and Sicily ?). There are some recent initiatives to reforest Iceland, but it will understandably take many decades to repair the damage.
I definitely have looked into Norway, though it is one of the most expensive places to live.