search fields not there without admin permissions

Environment: Windows 2003 server with terminal services. Internet Explorer 6.x (server has all ms updates applied)

User accesses terminal server via remote desktop connection software.

If a user has standard "domain user" permissions: When they try and perform a search, the window appears but the left hand column is blank. There are no fields where you can type in your search criteria - just a blue backdrop.
Also, when they go to certain websites that have a link that pops up a new window, the "popup" does not work. Right-click and selecting "open link in new window" fails also.

HOWEVER, if the user is granted "Administrators" or "Domain Administrators" permissions, all of the above works fine.

Does anyone have any ideas?

PS The server has 2 partitions C (system) and D (data) Both partitions have been shared at the root and full rights given to "Domain users" including sub-folders.