Scratching my head...
I verified libmysqlclient18 is installed when the libmysqlclient-dev package in installed. I verified that mysql_init is present:
nm -D /usr/lib/x86_64-linux-gnu/libmysqlclient.so.18.0.0 2>/dev/null | grep mysql_init
0000000000036ac0 T mysql_init
0000000000036c90 T mysql_init_character_set
I completely removed anything related with mysql: mysql-server, mysql client, any mysql core pkgs and libmysqlclient-dev. I then reinstalled the libmysqlclient-dev package and verified again that mysql_init was present, and I still ended up with the same error.
I moved to my desktop running precise and everything built and installed fine. I have to assume it has something to do with precise on my laptop. I will try the ubuntu forums.
If any of this triggers something that you might think would be worth a try let me know!!
Thanks for taking time