Well, I'm not sure what exactly is causing it, because in the past couple hours I have checked a dozen different sites, spread across numerous different servers using various hosting configurations, including varying operating systems and varying server software ... and all of them are showing whos-online data, including cart contents, properly, on Zen Cart v1.3.8.
So ... in some respect, the problem seems to be isolated to the two of you.
Architecturally, the data is stored in the sessions table if you have your configure.php settings set to do so. As mentioned previously, if you have your config set to store sessions in files, that's not going to work. And, you need to be sure you have the same setting on both the admin and the storefront versions of your configure.php file.
Additionally, if the problem "just started happening" recently, then it's pretty clear that the problem isn't with the software, unless you (or someone) have made changes to the software. So, if it's not the software, then perhaps it's the server. You're on your own to deal with your hosting company about what they've changed on their server.