Building the native extension does not work correctly when using RVM.
Manually adding the lib path like so https://github.com/milgner/memcache/commit/474a45ecb88e49d948c0c499a626c54e8160c5be
did the trick. This of course is no solution but I don't know enough about extconf to get the correct path.