Are you able to SSH in to your RHEL machine from your laptop?
The logs would be useful from both sides to see what is happening. Please follow the instructions here and either attach them to your reply or forward them to issues[at]nomachine.com.
If you have had issues connecting to a 3.5.0 server from a version 4.2 client, you should submit further information via the link above. 3.5.0 issues are dealt with via the traditional support channels whereas the forums are dedicated to version 4 server/client questions.