I tought that maybe some environment variable which is set when a normal user runs "sudo /etc/init.d/memcached start" happens not to be set when it's run during boot.
To prove the theory, i exported some interesting vars towards the start of /etc/init.d/memcached ... and it starts fine! (this also works as an alternative workaround).
This may be the solution of a number of reported bugs for various versions... I grepped for ENV in /usr/share/memcached/scripts/start-memcached and getenv in package source, but found nothing interesting, so I assume it's some linked library that misbehaves... but unfortunatlely have no time to nail it down!
In case you like my workaround more than the previous one, vars i defined just below the comments in startup script are:
(replace my login name with yours!)
# Short-Description: memcached - Memory caching daemon
# Description: memcached - Memory caching daemon
### END INIT INFO