What's the physical wiring of your sensors look like? There are some app-notes from Maxim/Dallas that discuss overall network topology and the limitations you'll run into with wire length, as well as some mitigation strategies. I don't have the app-note location handy, however. I ran into similar problems as you when wiring sensors up in my house and ended up having to run two separate networks. That may be the case for you, as well...