For me that game was the Witcher 2, I couldn't remember all the things in the tutorial to save my life, hell I think even died during the tutorial and the game recommended I play on easy.  Not even the souls games kicked my ass that much.  I hated the menus, there was like 15 sub menus and each of those had sub menus and I was just overwhelmed, it was so cluttered and there was so much.  I took some time off after the tutorial and came back to the game and there was so many little things like I couldn't remember like what the spells did just from looking at the weird symbols, what meditating did, which sword killed what and I just gave up on the game.  I really wanted to get into the game from the great reception it got, but I just couldn't do it.  

So has any game been too complicated for you?

At first, any game that uses crafting/combining items to get powerful new items, yeah because of that I was so afraid to play MMOs or MOBAs, but now, it's not too complicated, any game without those I can handle quite easily(I think).

Xenoblade almost was, BUT you don't have to make use of a lot of peripheral stuff to get through so I was able to pace myself and pick up stuff as I went.

But the Civilization series...nope. Just nope. Probably could have figured it out but honestly do not have the patience for it :P .

Honestly, when Majora's Mask came out (I was 9) I couldn't for the life of me figure out how to progress further through the game after getting the Zora mask without a walkthrough. The sidequests/masks I also had a hard time with figuring out on my own.

The Witcher.

I don't think there are games that are too complicated. There are only shitty tutorials.

Kids these days with their tutorials! 

/me is totally ignoring his ludology training which highlight Super Mario Bros first level as the ultimate tutorial, and his personal academic analysis of the first level of Super Mario World which reveals its execution of those concepts and was his first game as a kid.

Challenging yes, but never to complicated.

Only if "Trial and Error" is your choice of tutorial. First level of SMB is pretty much all T&E. No explanations given whatsoever and you will die if you have the wrong assumption.

Some niche Japanese RPGs with no tutorial at all. Blazing Souls -Accelate comes to mind...

I tried to play this on the PSP. Without the internet, I am sure I would still be stuck at the very beginning of the game.