I cannot say whether this is still an issue with you .. however, this recently occured to me too.
Run your task manager and select the processes tab.
You'll most likely already see
ehrecvr.exe along with
ehsched.exe (receiver & scheduling services)
What's Missing is
The Media Center Media Status Aggregator Service. It
also needs to be running.
IT IS
ehmsas.exe .. located at ...
C:\Windows\ehome\ehmsas.exe
I simply opened the eHome folder and clicked it once
(while viewing the active processes in WindowsTaskManager for verification it HAD started). This resolved the problem manually. I scheduled a tv recording and WaLa .. IT began just as it had been scheduled.
I further added ehmsas.exe to my Windows 7 Professional Quick Launch folder as I may need to manually start it until I can determine what's needed to auto run it at startup. You'll need to speak with a more seasoned member for those details. I'm justa schlubnozzle

who reads a ton of tweaker webpages.
oo & You look a lot like S.MARTin .. He was great back in the day!
[ehmsas.exe - Media Center Media Status Aggregator Service]