Eh ahí el problema, para eliminar una cookie se debe establecer bajo el mismo nombre pero con fecha de caducidad pasada.
Código PHP:
setcookie('clave', '', time() - 3600);
Por eso es bueno siempre, repito, siempre leer el manual antes de empezar a indagar y programar.