A. First check that you haven't given locks a fixed number rather than letting it automatically expand (the default) - check sp_configure.
If dynamic allocation is set, then this does work - it does dynamically allocate them as long as there is ENOUGH MEMORY to allocate them from. The error should really say that SQL has no more memory to allocate the locks from.
If you have artificially limited the amount of memory SQL Server can get then consider putting it back to an unlimited maximum and let it handle it itself. If it is already automatic then you will need to reduce the memory requirements of the queries/workload concerned or add more memory to the server.