Maybe a stupid question, but are you sure you installed the development files? I don't know about Redhat, but for Mandrake 9.1, the development files seem to be in libbzip2_1-devel-1.0.2-13mdk.i586.rpm.
(These files are of course not necessary to have bzip2, so you probably do not need to do anything in particular to get konstruct to know about /usr/bin/bzip2.)