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.