This is apparently a known bug in Windows 2008 SP2 and Vista SP2, so it is surprising that Microsoft has not yet fixed it.
If you have this problem here is how to fix it.
- Open regedit (start -> run -> regedit)
- Navigate to HKLM/System/CurrentControlSet/Services/Tcpip/Parameters/Interfaces
- Locate the Interface that is having the issue.
- Right click on Default Gateway and click Modify.
- You will notice that the first line is blank and that the correct gateway is on the second line. Delete the blank line and click OK
- Reboot and the problem is resolved.