From KevinWiki

Known Bugs

Although normalize-audio is installed and available, K3b cannot find it and keep asking to install it (sudo apt-get install normalize-audio). There is a workaround for this issue.

create normalize-audio in the /usr/local/bin/ and put the following script.

#!/bin/bash
case "$1" in    
    --version)
        /usr/bin/normalize-audio --version | sed -e 's/normalize/normalize-audio/g'
        ;;
    *)
        /usr/bin/normalize-audio "$@"
        ;;
esac

make it executable.

$ chmod a+x /usr/local/bin/normalize-audio

If it doesn't work, open K3b -> Configure K3b -> Programs -> Select the "Search Path" tab -> move /usr/local/bin/ up to position it before /usr/bin/.

Reference

http://machine-cycle.blogspot.com.au/2011/04/fixing-normalize-audio-feature-in-k3b.html