Hola Jorge011:
 
Algo debes de estar haciendo mal, porque esto se puede hacer perfectamente. Te dejo el script de cómo se haría desde una consola de texto, pero igual y te recomiendo que utilices alguna herramienta gráfica. Recuerda que los campos llave TIENEN QUE SER EXACTAMENTE DEL MISMO TIPO Y LONGITUD. Revisa este detalle. si checas el script se declaran dos FK (una para cada campo). Tu error también puede estar en que quieres asignar ambos campos con un sólo FK.     
Código MySQL:
Ver original- mysql> #Creamos las tablas de ejemplo 
- Query OK, 0 rows affected (0.06 sec) 
-   
- Query OK, 0 rows affected (0.08 sec) 
-   
- mysql> #Creamos la FK del campo idUsuarioEnvia 
- Query OK, 0 rows affected (0.13 sec) 
-   
- mysql> #Creamos la FK del campo idUsuarioRecibe 
- Query OK, 0 rows affected (0.13 sec) 
-   
- mysql> #insertamos valores a la tabla de usuarios; 
- Query OK, 2 rows affected (0.00 sec) 
-   
- +-----------+--------+ 
- | idUsuario | nombre | 
- +-----------+--------+ 
- |         1 | uno    | 
- |         2 | dos    | 
- +-----------+--------+ 
-   
- mysql> #insertamos un mensaje correcto 
- Query OK, 1 row affected (0.05 sec) 
-   
- +-----------+----------------+-----------------+-------------+ 
- | idMensaje | idUsuarioEnvia | idUsuarioRecibe | mensaje     | 
- +-----------+----------------+-----------------+-------------+ 
- |         1 |              1 |               2 | mensaje uno | 
- +-----------+----------------+-----------------+-------------+ 
-   
- mysql> #Verificamos la integridad de la columna idUsuarioEnvia 
- mysql> #Verificamos la integridad de la columna idUsuarioRecibe 
- mysql> 
Saludos
Leo