So OpenSUSE turned out to be very unique in having a
libmysqlclient-devel package that worked with Amarok.

Summary on how to build MySQL for Amarok 2:
* Download http://dev.mysql.com/get/Downloads/MySQL-5.1/mysql-5.1.28-rc.tar.gz/from/http://mysql.osuosl.org/
* tar -xzvf mysql-5.1.28-rc.tar.gz
* cd mysql-5.1.28
* cp -R /path/to/amaroksource/supplementary_scripts/mysqle/* .
* ./build-mysql.sh --prefix=${HOME}/usr
* then build Amarok like normal

I haven't actually tested this instructions. Lets use this thread to
help each other build MySQL embedded. :)

Ian