Can you drive a car? Can you open a door without thinking about it? Can you sing? Can you whistle? Can you move a mouse pointer to where you want it? These are all muscle coordination tasks that bypass conscious thought completely.
What may have been happening is that you are getting frustrated too soon. When I started learning to blind-type Colemak last year, I was cursing for nearly every letter that I typed. However, I persisted, and switched to Colemak full-time once I could do 20wpm. Still very frustrating. Now, a year later, I type around 50-60 wpm which is fast enough for programming. My typing speed curve is pretty much linear, interestingly.
I trained pretty much daily in the first couple of months, using http://keybr.com, just before I went to bed, so that I couldn't really concentrate on it and it was mostly on auto-pilot.
Switching to Colemak at the same time as learning to blind-type properly was a good idea I think, I didn't have a keyboard to look at and any wrong muscle memory from qwerty was bypassed.
So basically I am being a condescending bastard and claiming that if you can breathe in and out, you can learn how to touch-type