If you're using transparent mode to send the data, this can happen. The packet can get split into two and you get a mess. If you switch to api mode, use the XBee library and be sure to check the checksum on the packet. This kind of thing most often happens when you have the baudrate set high and are really putting the data into the XBee rapidly. It also happens when you have a number of XBees and there isn't enough guard time for the devices to sync up properly.
The latest XBee library supports software serial quite nicely and can help you with this kind of thing. Hunt around though and make sure you have the latest library.