I have some Windows server 2012 + SQL Server 2012 combinations both in the lab and in production, and they work without issues (well, without this issue :-D).
I actually just created a new local user on the lab machine, left it as a member only of the Users group, stopped the Agent, changed the Agent to use the new user, and started the Agent with no issues.
Just to make sure I'm clear on your situation:
1) You are currently only receiving the generic "Service failed to start in a timely fashion" error?
2) Does this occur no matter what account you specify for the Agent?
In the meantime I'll see if I can recreate your issue, but I've had no success so far.