This may sound silly, but are you 100% sure you're editing the right theme?
You mentioned design, so I'm assuming that's mainly what you're doing, right? I didn't know if you were using the theme editor, or manually changing things some other way.
Actually, if switching themes works, that would seem to indicate the problem... or a theme switch wouldn't stick either. If you can see a theme swap, you should be able to see anything else that changes.
Maybe put a comment in the header, then go through themes, refreshing each one, then checking the source for the comment.
I would think the db could be eliminated as a problem by simply making a new post/page and see if it shows up.
Also, is this a fresh installation, or a fresh problem on an old installation? If it's a new installation, you didn't go the "easy" route, did you? I'd imagine you couldn't edit those templates, but I've never done the easy one, so I don't know if it gives you an option to do it that doesn't "stick" -- or if the option simply isn't there. I'm sure someone else could clear that up.