With proper dithering the banding that you get (in the sky, especially) could be mitigated a lot. For example Personal Paint can do a really good job of reducing a full-colour image down to 256 (or less). I'm however not sure how well it deals with HAM images, I never really used them much.
HAM modes are somewhat special in how they work, so any converter needs to be crafted with the limitations in mind. There have been discussions here on the forum regarding the best algorithm for the job. See here
, for example.