Si, pasa que puse el if al revés:
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 '<input name="agregar" type="submit" value="agregar" />';
else echo 'Yo Soy tu amigo';
?>
Negandolo debería funcionar