I've had this problem as well. However, it only happens for one person I try to send it to. This would be my brother who I primarily play games with. He had an older account before and we were friends when he used that account, but he decided he wanted a new name, so he created a new account. Now I send an initiation to be friends and it never goes through. We've tried both ways. I even tried deleting his old account off my friends list and it still won't work.