I've recently had a similar experience to what you've described above in trying to learn Haskell. I read Tim Sweeney's presentation on The Next Mainstream Programming Language and he mentions it frequently. I saw it mentioned a few other places as well, so I took the leap and tried it.
I hadn't felt stupid like that in years. It requires a completely different perspective and a very different way of viewing programming. I found myself, for the first time in years, unable to come up with any solution to some simple programming problem. Wrapping my mind around monads literally made my head hurt.
Luckily, Haskell's compiler encourages experimentation by rejecting most bad programs at compile time. Once I learned how to read the error messages and had written a few simple programs things began to click.
Within about a month or two of banging out my first line of code in Haskell, I'd written a complete interpreter for a little language (the small, esoteric, but Turing complete whenever language) including a formal parser, all in Haskell. I'd never done anything like that before, but Haskell made it remarkably easy.
I haven't done anything in Haskell lately, but it has doubtless expanded my understanding of programming, and whenever I need a little bit of humbling, I try to read up on some of what's going on with Haskell.