Here's another thought:
What's with friend-requests?

For example:
A requests to be friends with B, but needs to wait until B approves.
You want to record this status as a "possible (mutual) friendship" and then convert it into a "mutual" friendship when approved.

My first thought would be to simply add another column to the friends table as proposed above, like
Friends(user_id, friends_user_id, how_do_you_know_eachother, status),
where "status" could have values like "requested" and "approved".

Hm...