I've been looking into changing our DHCP range at work, and stumbled onto this gem of a windows issue.
Whenever I received an IP from the new range, I would have to manually set my connection to "Work" network. Fearing that I'd have to visit every PC if we changed the DHCP range, I did some research.
Microsoft says that if you're PC is connected to a domain, the network type should be set to "Domain", not Public or Work or whatever else. For some reason, my computer wasn't automatically being set to the right value.
It turns out that the Windows Firewall service is crucial to managing this setting. Because I'm a dork on a slow PC, I had manually disabled a few services that were set to run at startup - including the Windows Firewall! After re-starting this, everything worked as expected.
Since this was neither intuitive nor easy to find, I'll note it here for posterity.