Arduino Uno: SoftSerial For Two Devices (em406a GPS and DS18B20 Temp Probe) Not Quite Right
You probably have clashing interrupts.

While there isn't really any reason this couldn't work, you are going to need to dump the arduino environment, and probably spend some time refining and modifying the ISR (interrupt service routines) in the various libraries. 

Basically, the arduino stuff lets the libraries do a lot of set-up work that's effectively hidden from you. Unfortunately, some of the libraries are stomping on each other.
The only solution to this is to actually understand what the libraries are actually doing, and modify one or both of them to prevent them from having conflicts over the AVR's resources.