Are you sending the data one byte at a time, and checking the CTS?
Or are you sending the whole packet then checking the CTS?
The CTS flag is active when there are only 16 bytes left in the buffer on the xbee. Though you have to take into consideration that your uart driver/module might have a buffer of its own. In that case, you might fill up your local buffer, and by the time the CTS flag activates you have 16+ bytes in your buffer that is still trying to dump into the XBee buffer. Thus causing the buffer to overflow. Then the Xbee buffer has been overwritten, thus messing up the packet structure.
That is how you could be losing data.
Check to see how the hardware handles CTS/RTS.
If it is still not working, try it without any buffers in the uart driver/module and listen to the CTS line yourself. Try it byte by byte, it should work then.
Obviously, you’ll want your uart driver/module to handle the CTS line for you, but you probably don’t have it linked up correctly.