This is a fallacy. The gross debt of Icelandic private and public economic units has not been rising because the krona has fallen as spectacularly as it has but the other way around: the krona collapses because the gross debt of Icelandic private and public economic units is increasing. And I emphasise the word private!
The following graph describes the correlation and causality best. It shows that if the gross debt of private and public units in Iceland increases, the exchange rate weakens against the US dollar. The correlation over the whole period (no lags) 1972-2007 is 0.80 which is very high for such a long period. If the change of the USDISK cross (the number of ISK in one USD) is lagged by one year the correlation is unchanged. If the change in gross debt is however lagged by one year against the change in USDISK cross, the correlation goes down to 0.48. This implies that the causation is a lot stronger from increased gross debt of private and public units to the depreciation of the ISK rather than ISK causing gross debt of private and public units to increase.
Annual change in domestic gross private and public debt held by the financial system and the annual change in the nominal exchange rate of the ISK against the USD. Notice the high correlation
So the problem is not the currency or what currency Iceland uses. The problem is the expansion of debt, public and private! And since banks have always the incentive to expand debt in any economy or under any currency regime they work under, for the simple fact that they increase their profits on the interest difference of simultaneously created deposits and loans, the ISK will always depreciate over time if the banks are allowed to pump out credit according to their own will. The devaluation of the krona happens as the necessary restoration of international competitiveness has to happen after a period of binge credit expansion. If the economy uses a foreign currency, the banks will still have the incentive to pump out credit as they see fit - still leading to over expansion of private and public debt - and the devaluation that is needed to restore the competitiveness of the economy will have to be internal through lowering of nominal wages, i.e. Greek-style.
Nobody wants to see any kind of devaluation, not of the nominal exchange rate or of the internal one. But if the credit expansion of banks is not kept at bay at all times, either one will always happen. Changing the currency regime is futile in fighting the banks' incentive to expand credit.
Of course, we can change the currency regime if we want to. But if we do, we better realise that if we don't limit the ability of the banking system to expand credit in the economy, we will have to go through an internal devaluation sooner rather than later under a fixed exchange rate regime.