I agree, follow should always remain an option unless one user blocks another, regardless of friendship status. 

Sounds like something on your site though... I see the ability to follow without being friends on my site. Tim Burleigh have you come across this at all?