The critical rebuild patch is windows only, Hip. The 1.69 linux patch does the same for the nwn Linux client, though.
Regarding the keys - are you sure everything is the way it should be? There was a known glitch with entering the keys when using the Linux client that leads to entering the NWN key twice, because the nwncdkey.ini file is written in a wrong way, but I don't know if that is still the case. But you can enter the keys into the ini file directly - open the file in any text editor and make sure it looks like this:
[CDKEY]
Key1=<Your-NWN-Key>
Key2=<Your-SoU-Key>
Key3=<Your-HotU-Key>
If this does not solve your problems, then something with you installation went wrong and we will need more information to troubleshoot - like what version of nwn do you have? Diamond? GoG download? Which Ubuntu version, which type of graphics board, etc. - you get my drift.
Greetings
Skildron