SharePoint service configuration fails on Windows Server 2008 R2

I am building a SharePoint test farm with SharePoint server 2007 Enterprise based on Windows Server 2008 R2. There are 3 different virtual machines (Hyper-V), all in the same domain, UCTEST. When I installed SharePoint and ran the configuration wizard, I entered a domain account (svc_sp) as the main farm / central account, which worked perfectly.

Now, in Central Admin, I try to go through the administrators tasks list, and in the assign services to servers task I try starting the Windows SharePoint Services Search service. I enter 2 separate user accounts for the search and content access parts. The user's exist and are in the same organisational unit as the main farm account. But when I click start I get an Event ID 4625, audit failure.

The error message is the following:

An account failed to log on.

Subject:

Security ID: UCTEST\Administrator

Account Name: Administrator

Account Domain: UCTEST

Logon ID: 0x98828

Logon Type: 3

Account For Which Logon Failed:

Security ID: NULL SID

Account Name: svc_sp_wsscontent

Account Domain: UCTEST

Failure Information:

Failure Reason: Unknown user name or bad password.

Status: 0xc000006d

Sub Status: 0xc000006a

Process Information:

Caller Process ID: 0x364

Caller Process Name: C:\Windows\System32\inetsrv\w3wp.exe

Network Information:

Workstation Name: UCTEST-UC01

Source Network Address: -

Source Port: -

Detailed Authentication Information:

Logon Process: Advapi

Authentication Package: Negotiate

Transited Services: -

Package Name (NTLM only): -

Key Length: 0

P.S. Thinking it could be SQL related i have made all service account securityadmin and dbcreator on SQL Server (2008 SP1)

P.P.S. All users needed are added to the "logon as batch" / "logon as service" in the local security group policy.

Deleting the user accounts and recreating them seemed to do the trick. Tried logging on to the machine as the service account didn't work, so i figured there had to be something wrong with the account. deleted it, added it, now it's all working again..