Estás seguro que con quien lo compruebas tiene algún amigo para que no te deje agregarlo.
Si es así haz un echo de los id, el de la session y el otro para comprobar que tengan el valor que quieres.
Y mejor pon este cófigo:
Código PHP:
<?php
$amigo = mysql_query("SELECT * FROM amistades WHERE (id_de = '".$_SESSION['id']."' AND id_para = '".$id."') OR (id_para = '".$_SESSION['id']."' AND id_de = '".$id."')");
if(mysql_num_rows($amigo) > 0) echo 'Yo Soy tu amigo';
else echo '<input name="agregar" type="submit" value="agregar" />';
?>