I have stumbled upon a problem with Konsole being incapable of showing 256 colors. The Linux distribution I have experienced this particular problem is Mageia. It turns out that you have to do two things.
First, make sure you have ncurses-extraterms installed. You can install them (as root) in Mageia as follows:
After doing this open Konsole and go to menu Settings -> Edit current profile -> Environment -> Edit and then add or substitute line beginning with TERM= as follows:
Restart your Konsole and you should be ready to go.