I use VoIPCheap on 3CX with no issues. Setup was simple using generic template, nothing unusual. I would suggest rechecking ID, Password, SIP and STUN server entries for errors. If a screen print of my setup would help just let me know.
If you are receiving such an error it means that proper SIP comunication between your PBX and the provider is in place.
I would recmend you focus on the line (account) settings of you provider and like Aaron mentioned recheck the ID and password as it is the most likely cause of this failure.