Microsoft offers free support for problems caused by Windows Update.
I've done an ASR on Windows Small Business Server 2003 a couple of times.
There are a couple of limitations that can cause trouble:
1) The hard drive you are recovering to must be the same size or larger than the original.
2) You need a floppy drive on the server being recovered.
3) You must restore from a tape drive or from a LOCAL hard drive. If your backup is on a USB drive, you must remove the drive and put it directly in the Server.
4) If you are using a RAID card or tape drive that doesn't have drivers in Windows Server, then you may find it easier to just install Windows Server, update it to the same Service Pack as you were on when you made your backup, and then restore your data and system from your backup.