Ok then, first thing I would do to troubleshoot is narrow down the problem, can anyone else see your changes that has never viewed your site before? If not, then its a real problem and not a caching problem.
I just try to sort out the easy solutions first before digging into code
Although it sounds like this isn't a caching problem, I have had stranger things happen