Hello BeZazz !
Please specify two things:
1) Do you have this trouble only with friend requests? Are other messages sent fine?
2) Do you use any SMTP?