Jon, as with any automation just make sure that your logical criteria and actions fit 100% of the time, and you aren't going to for example miss recordings (like back to back HBO) or you're rebooting when something else is going on. But if what you are asking for is that straight forward then it should be relatively easy, logically speaking, to implement.
There are a few ways to do this, like creating an active monitor process, etc. But I usually prefer to use as much of what is native to Windows before writing custom stuff. Therefore, I would suggest starting with Windows Task Scheduler. It has a trigger option for Event Log entries, and you create a new one that fires from the Media Center recorded event. However, you can't get granular to parse out the message such as HBO in the text, so instead you run a PowerShell command after every recording to go back into the Event Log and look for the finished recording Event.
Within PowerShell you can parse out Event Log message text, so if it doesn’t have HBO in the message then exit out. If it does, then schedule the reboot.
You can schedule the reboot within the PowerShell itself. Or there are two different ways from the command line, which is what the PowerShell will run when it detects HBO recorded. For the command lines, either create a new scheduled task for the 4am reboot. Or calculate how many seconds from now is the next 4am and then run the shutdown command with a wait that number of seconds. The latter, or native PowerShell restart, are cleaner because you don't have to create another scheduled task in your system, but the former is actually easier because with Task Scheduler you can just specify a time. Actually I need to check more on that one because you may still need to calculate the current date and add a day if it's before midnight, or not it after midnight. Or maybe Task Scheduler just does it for you from the command line. Hmm, maybe either method you’ll need to calculate. For the native PowerShell restart, you'll still need to calculate when.
You can also create the Scheduled Task within PowerShell, but same potential calculations would apply as the command line.
Alternatively, instead of Task Scheduler you can use the EventTrigger command, but it no longer offers much advantage over Task Scheduler since Windows 7 because it can now trigger off of Events. Plus it is easier to administer through the UI. VBScript is an alternative to the PowerShell I mentioned above.
I realize I wrote a bunch, but it is actually pretty simple. In summary, create a Scheduled Task that triggers from Media Center Event log recording success, and then the action is to run a script, which determines either to do nothing or restart x seconds from then.
Let me know if you need any assistance with any of this.