There are a number of things to check and establish in order to resolve this issue:
Is Profile freezing no matter what task is being performed or is it only when doing something particular such as searching? If it is a particular task inform support of this as it will make resolving the issue quicker.
Is it actually all users or just certain users with the issue. If it is only certain users, are these users all using the same terminal server? If so that particular terminal server should be investigated rather than the database server.
If all users are affected then the database server will need to be investigated.
Run some ping tests from users' PCs to the database server. Your IT or Profile support can assist with this. If the pings are high or timeouts occur the issue will be a network issue, which your IT can investigate further.
If the ping tests are fine check the performance on the database server. Check for high use of memory or CPU. Anti-virus scans often cause slowness also, so these should be scheduled outside of working hours.
If you have checked everything you can from the above, please raise a new case online and reference the title of this article.