All headers need to be sent before any output to the browser... this includes spaces before the <? in the start of a PHP document or any print/echo commands or any PHP errors sent to the screen. Headers come first.
This is similar to an HTML doc with the 'head' section coming before the 'body' section.
The top is an excellent place to add cache-control headers, but be very certain that there is no output to the browser before the headers are sent or it may generate an error (white screen).
If a page redirects somewhere (possibly in the future), it needs to send the cache control headers before issuing a redirect status of 3xx. Otherwise the redirect may be permanently cached in the newer browsers, even if the page returns later.
If you still experience an issue immediately after implementing this, this is normal with a 'tainted browser'. Clear your cookies and cache, then try the page again. It will no longer be cached in your browser and will no longer be cached in fresh browsers visiting your site.