This may be a stupid (sorry) session call that matches sessions over IP. All your NAT users have the same external IP address, so they are combined. Better to use cookies to handle sessions.
As beliarius says, you may already be using cookies, but if cookies are created from IP, they are very useless.
If the application you are talking about is not browser-based, you will need to send cookies to your customers and you will have to process the cookies for yourself. Or simply use one TCP connection for each client and reconnect to the reconnection.
source share