Did the tech check your signal or just replace the boxes? A weak signal could affect both TV and Internet and replacing boxes wouldn't fix it.
Is being unable to schedule a program the only issue with the DVR? Can you manually record a program? Prior to exchanging the boxes, did you have any changes made to your TV plan? A change may have accidentally been made that removed your DVR service. If so, you'd be able to watch live TV, but you wouldn't be able to record programs either by a schedule or manually. When you email cox.help@cox.com, ask them to verify you have DSR service enabled.