Ok, just to check.
1) Have you rooted the Android device?
2) Have you downgraded the REX firmware so it uses USB-TCP/IP?
3) What does lsusb tell you?
The Android documentation is almost non-existing at the moment, but here are some instructions: http://developer.tobii.com/rex-firmware/