Your distribution is quite old now. It's better for you to upgrade to the newest version which is Ubuntu 8.04.1. After the upgrade you can easily install KDE4. At below, you can find a step-by-step upgrade process guide for your Ubuntu version.
http://www.ubuntu.com/getubuntu/upgradingPS: Don't forget to backup your important data before upgrade!
Good luck!