Actually you can make major changes to appearance with the style sheets though it does require a very thorough knowledge of positioning and/or float behaviour. Part of the problem is that most "skinners" cut their teeth on systems like phpBB and are used to accomplishing what they want with markup rather than css. The downside is that the markup needs to be heavier than strictly necessary because it has to be reasonably flexible.
I'm also not convinced that people who want to make major changes to the markup were PunBB's intended audience. If someone has a definite requirement for a templating system then why are they looking at PunBB in the first place?
Having said that one thing I would like to see introduced is custom .tpl files for styles as per codeXP's mod. That introduces a lot of flexibility for no overhead whatsoever. Its a very PunBB'ish thing to do as it is simply making the most use of features already available. AND I REALLY DO MEAN THIS