Delays When Updating Site

Just wondering if anyone could shed some light on my situation. When I update my site’s appearances or theme options it doesn’t seem to apply it to the “live” site properly.
For example, yesterday when updating my backgrounds, the home page would have a different background than the rest of my pages. Or the homepage would be red, two pages would be pink, and a 3rd page would be grey. When I went to the site this morning it appeared to be fixed and all backgrounds were consistently grey. This happened as well with my logo where on one page only the image was broken. Eventually after playing around it seemed to “fix” itself and appeared on all pages.

– I had cleared the chache on all browsers
– tried viewing the site on other computers
– tried deleted logo images and re-uploading