Попробуйте сделать это следующим образом:
$sql = <<EOL
INSERT INTO USERS (`FBID`, `FIRST_NAME`, `LAST_NAME`, `GENDER`)
VALUES ('$fbid', '$firstName', '$lastName', '$gender')
EOL;
$stmt = mysql_query($sql) or die("MySQL error: " . mysql_error());
Это сохранит запрос для вас в $sql
, так что вы можете повторить его в другом месте и посмотреть, что на самом деле было произведено.