CMD + space not working in the first try
i saw this on a user's machine lately.  it was acting very strangely with a couple command keys.  

the solution here was to go to keyboard preference pane and clear out all shortcuts and restore defaults for each section.  it seems an app this user installed was grabbing the key-combo for its own purposes, and once removing the customizing it worked well.

it might be this simple in your case.