youtube
I just changed my YouTube channel’s name and if I visit the channel at its url, then I see the new name. In search, it still shows the old name and only comes up after searching for the old name. What do I do in this situation? How can I properly change my channel name? 
Tags (and, for that matter, HTML <meta name=keywords>) don't really get looked at by search at all, neither on YouTube nor on Google and most other search engines. They do get used for related videos though, and YouTube from time to time experiments on making them more useful (like the "tag sections" you mentioned that since have been removed again), but as of now, videos only containing the search term as tag don't show up in search.
Attack this from the outside.
Use Google's filtering capabilities.
For example, let's say I wanted to search for videos by user "MyAbridged" posted in August, 2012.
I search for myabridged site:youtube.com to get videos by that user.
Then click Search Tools and you will see Any Time come up as an option.
Finally, click Any Time, choose Custom Range, and select the time frame you want to restrict your search to.
Complete your search and you now have all the videos posted by that user in that time frame.
Example search: myabridged site:youtube.com between Aug 1, 2012 and Aug 31, 2012
Note that this search technically searches for any pages within Youtube that mention the name "MyAbridged" anywhere in the page, so it will actually return back more than just their videos, but it will get you where you need to go
Best Answer
It will take a while for your new channel name to be updated across all Google sergers. Give it some time and you’ll see your new channel name show up in search.
I changed my YouTube channel name as well and noticed it took a while to update site-wide.