Hi Dan,
I better understand now! :-) The huge number of users is the source of your problem. The Store module use standard DNN API to get the users list, then you could encounter similar problems with other modules and even DNN.
The Store module can run with different modes, one of them allow to order without having a DNN user account. In this mode, orders have to be linked to an impersonated user account defined in the Store Admin module. That's why you can't start normaly the Store Admin module, because the interface try to fill a dropdown list with user accounts to select this impersonated account.
I could try to ask for a role, then get users from the selected role to fill the dropdown list. Whatever the workaround, you could avoid this kind of problem if you try to increase the timeout value in your web.config file. By default, ASP.NET automatically kills a non responding request after 90 seconds. If your SQL Server instance is too slow because a huge db and/or a too slow server hardware then any long request will fails! Also, you should read my last blog post. I suppose that your users have been imported, then your log file could be huge and this can slow down SQL Server access!
Please give me a few days to apply the workaround (asking the role at first) and send me an email, I will send you a beta version when this will be done.
Gilles