SQL "login failed for user [username]" error for windows service, but SSMS login works

It's working! Finally!

First, using Kevin's suggestion (comment underneath the original question), I checked through the SQL Server Logs (in Management Studio, expand server, expand Management, expand SQL Server Logs). This is how I found more lengthy error reporting that helped me diagnose the issue.

Turns out the server didn't allow anything other than Windows Authentication, so that's why my attempts at entering the UN/PW manually failed.

However, I still had the issue where the server was passing my machine name as the user instead of my username. This was fixed with Duncan's suggestion of changing the user that the service ran under to my name (right click in Services->Properties->Log On Tab).

Thanks to everyone for your help, much appreciated.

You need to check the user account that the service is running under. By the sounds of things it is running as Local System which will try and pass the machine name through as the login.

Try changing this to a least privileged domain user (or for testing, you could use your own account) and then granting that user a login to the SQL Server. That should do the trick.