In none of these countries were people surprised that I could speak their language (even after a few months).
I meant that average people in those countries couldn't communicate on the level that you deem necessary... not the language thing. Sorry if I was unclear.