Please, first make sure that what Mike said is done.

I would say it does not look as permission problem from the error message. The error mesasaage looks like that instance could not be found and I always have this message with firewall problems, no matter who started the SQL services. It was only 2 cases where access was actually denied.

You do know that instances listen on different ports. Use Server Network Utility to check ports. Are you logging in from the same machine where the server is installed? did your users tried to use it from other computers? Instance should be accesses as MachineName\InstanceName

Additionally if users and you and the server are in different domains please, let them use fully qualified domain name like MyServer.Domain.MyCompany.com or whatever is on your DNS server for this machine.

Test both TCP/IP and Named Pipes for connection. Make sure network protocols are enabled in SQL Server. You may be using Shared Memory (LPC) when accessing from the same computer. Check in the Current activity Window Processes view what protocol is used when you are connected.

Any of what I listed usually produces your error message.

Replace your Domain account for SQL Startup with something else. Your account will lock out as soon as you change your domain password.

Yelena