lsof -i as root and confirm that the memcache daemon is running on the port you listed.
Formatted for sanity:
memcached 16526 corneliu 31u IPv4 207975 0t0 TCP *:memcache (LISTEN)
memcached 16526 corneliu 32u IPv6 207976 0t0 TCP *:memcache (LISTEN)
memcached 16526 corneliu 33u IPv4 207979 0t0 UDP *:memcache
memcached 16526 corneliu 34u IPv6 207980 0t0 UDP *:memcache
So the memcache server is listening on both TCP and UDP for both IPv4 and IPv6. I assume that the /etc/services entry for memcache is port 11211. Service is listening.
Manually verify the server responds to commands
I'd reference this question: http://stackoverflow.com/questions/6045187/memcache-connects-but-doesnt-respond-to-any-command and verify that the server is responding to commands that you send via telnet or netcat. It will probably also be very helpful if you run tcpdump or wireshark to capture the network traffic and actually see what packets are traveling.
Debug things without changing the memcache configuration first. Attempting to change the server's bind address per that question above should be the last thing you do. Let me know your progress.