The "Reload Required" would also be normal after installing an SU on the IC server - the SU includes new firmware for the phones, and they require a reload to receive the new firmware.
The reboot of all the phones a few days before may very well have been initiated by the POE switch being unplugged briefly, maybe someone doing maintenance on the switch, or the switch losing power (presuming you have all the phones connected to a POE switch for power).
The failure to contact the boot server is a networking issue, most likely. Presuming you are using Option 160 in DHCP to tell the phones where to find the IC server, check that setting to be sure it is correct. If you are running a switchover pair, and you are using the DNS server A records and service records to tell the phones where to find the IC server, check those settings as well and make sure DNS is finding the active IC server (ping the name/address listed in the DHCP Option 160 setting from a computer on the same subnet/VLAN as the phones to make sure you get a response).
Lots of things to check :-)