I think that having the right to do something doesn't make it the right thing to do. The right to free speech should be protected - I just wish that sometimes it was exercised with better judgment.
Jock is right when he says that it appears the goal here was to troll Islam. If the cartoons had editorial or entertainment value that was strong enough to warrant the offense given, then fine. But if this was just poking Islam with a stick, then I think it's pretty low. The extremist Islamic response and subsequent threats trump the poor judgment of the newspaper, but that doesn't excuse the newspaper.