As I've worked with web services, mainly WCF services, I've run into some really funky problems as I've consumed services that have made me want to rip my hair out. Hopefully this little bit of advice will help many developers keep more of their hair intact.
Update your service reference before getting too far into trying to diagnose the problem:
This is often required when a namespace changes in the service code even if none of the method signatures have changed. This has usually been the case when the service is mysteriously returning null when you know it shouldn't.