ciao
se non l'ultimo, tra gli ultimi tentativi.
mi è venuto in mente che la tabella relationship in fondo è quella che regola il tutto, quindi prova a fare una query del genere
SELECT M.msg_id, M.uid_fk, M.message, M.created, U.username, M.uploads FROM relationship AS R
INNER JOIN messages AS M ON (M.fuid_fk = R.user_1 OR M.fuid_fk = R.user_2)
INNER JOIN user as U ON (U.uid = R.user_1 OR U.uid = R.user_2)
WHERE (R.user_1 = '$uid' OR R.user_2 = '$uid') AND amico='S'
poi aggiungici gli eventuali order e limit
p.s.
verifica che abbia scritto bene i nomi dei campi e delle variabili
ps al p.s.
ho scritto riga per riga per non confondermi