I'm speaking with some experience, as, although I haven't changed my name, my wife has after we got married. In our case, the document confirming the name change was the marriage certificate, but for all intents and purposes it doesn't matter.
The matters were a bit more complicated for us, as we didn't get married in the country we live in (UK) but instead in the USA. Furthermore, my wife at the time was a Russian citizen.
Here's the quick run-down of what had to be done. With the marriage certificate in hand in the USA, we got it apostilled in the USA. We travelled back to the UK on her passport with her maiden name - this is obvious, as the name on the ticket matched the name in the passport nobody really cared.
When we arrived to the UK, we translated the certificate and the apostille and certified the translation in the Russian embassy. With the translation in hand, she had to travel back to Russia (under the old name - again, name on passport matched the name on the ticket, so nobody cared) to change her passport there. This is where the fun started, as now the name in her new passport didn't match the name on her visa. When she arrived back to the UK, she presented her new passport with the new name, her old passport with the old name and the visa in the old name and the marriage certificate - this was it - no problems at all.
After that, she changed all the relevant UK documents to the new name (driving license, work ID, etc.) - and from that point onward we've travelled to at least a dozen different countries - with just the new passport. She had to get visas for some of these countries. On pretty much all visa applications, she had to state her previous name - but nobody ever asked her about any documents confirming the name change.
What mattered was that her passport contained her new name and her photograph. The only reason we had to carry the marriage certificate with us was to present on arrival in the UK, as the name on the visa didn't match the name on the passport.
So, to summarize, you should have no problems after the name change as long as you properly change your documents (most importantly, passport) in the country where you change your name. After that, nobody will ever ask you about the name change confirmation document.