When we patch our Hyper-V hosts and it reboots them they normally come back as the double green check saying patched but not rebooted. When we actually go check the server it is in fact rebooted or rebooting, it just takes a bit longer than other servers to reboot. I am thinking that Bladelogic is timing out on waiting for a reboot and is just coming back and saying it patched but did not reboot. Is it possible to turn this timeout value up?
On the Deploy Job properties, try setting the AGENT_CONNECTION_TIMEOUT or AGENT_QUEUE_WAIT_TIMEOUT to a higher value. 0 is infinite.