Thanks Eric. Are you saying you are using this exact shortcode?
[tubepress searchResultsRestrictedToUser=ptpamedia mode=tag tagValue=Actifry]
Can you think of any reason why it would work for you and not on our site? Here is a test page with the exact shortcode and it returns no videos.
http://ptpa.com/tubepress-test/
Thanks for posting that link to a test page. Turns out that I was seeing a different result because I was using a different sort order for the videos.
From what I can see, this is definitely a bug on YouTube's end. I've filed a bug report with them - please "star" that issue to both draw their attention to the problem and track updates.
Workaround.
You can configure TubePress to use the "random" sort order which, due to some underlying technical reasons, will actually cause the videos to come back in order of relevance (which is actually somewhat suitable for a search-based gallery).
In WordPress, you can set the sort order to "random" via WP Admin > Settings > TubePress > Feed > Order videos by. Or you can set it via shortcode:
[tubepress orderBy="random"]
Please give that a try and let me know how it works for you? I hope that it will hold things over for everyone until we get a response from the YouTube folks.