lo mejor es que uses un path absoluto:
Código:
http://www.mipagina.com/favicon.ico
De esta forma:
Código HTML:
<link type="image/x-icon" href="http://www.mipagina.com/favicon.ico" rel="icon" />
<link type="image/x-icon" href="http://www.mipagina.com/favicon.ico" rel="shortcut icon" />