It's a software issue that's been a problem for quite sometime, mostly with certain model HR24s. There's currently no work around, and I'm surprised techs have replaced your HD DVR as DirecTV has explicitly stated not to replace equipment if it's only a youtube issue that's been identified as a SOFTWARE problem, not hardware.
I saw this issue on Monday at a customer's house. Her HR24 dvr connected via WiFi Deca could do VOD, but youtube searches yielded the internet connection problem message. Tried the wired broadband deca, even the "no-no" direct ethernet connection, nothing worked. She understood it's a software issue and DirecTV will eventually fix it.
All of receivers are older HR21 & 22s, and they have no issues with youtube.