Major cache, cookie or session issue after upgrade to 5.1.5

[DisasterDotCom]

So I posted all of these issues over at vBulletin.com, and I also opened up tickets. The response from support (after 24 hours) was "Clear your system cache and local browser cache". This was the first thing we tried before we even opened up tickets, and I'm not getting love over there so I thought I'd ask for suggestions here as to how to track these gremlins down. I'm so close to switching to Xenforo (found someone who will custom move our site to Xenforo for under $200, including users, threads and ensuring our URLs all match). Anyway...

We "upgraded" from 5.1.4 to 5.1.5. We immediately started having the following issues:

1. If someone posts a reply to a thread and then goes back to the main forum page, the new reply doesn't show up as the latest (the topic still shows 0 replies). If they then go back into the thread, the reply doesn't show up until they refresh the page. Obviously a browser cache issue somewhere, but it's happening consistently across our user base and can be consistently reproduced.
2. When people delete notifications, they aren't actually deleting. The number at the top of the page decrements, but when you click on a new page it goes back up and the notification you deleted reappears.
3. When people click on certain links within the forums (local internal links) they are logged out (cookie issue? We tried deleting ALL cookies for the domain and still have the same issues)
4. When we go to /forums, the sub-headings of the menu (i.e. Today's Posts, Who's Online, etc.) don't show up, but they do when you go any other page (such as /forums/forum)
5. Using the search in the upper right corner of AdminCP logs the admin/mod out

These issues all seem to be related to a caching or cookie issue, or maybe a session issue somewhere. They are causing MASSIVE usability issues across our forums. Please help!