LOCK TIME OUT ON SQL 6.5

I am running on NT4 platform with service pack4, SQL6.5 with service pack 3.
Most of the time when more users on line & making a quary from tables which contains more 1.6 million records they end up saying lock time out. Please specify is there areany remedy for such problems. I have allocated 1GB Memory for sql where my server is having 1GB + 128MB RAM.

Thanking you