Did you rellay clear ALL the cache? How did you clear it? Form the admin interface or with clearcache.sh script? Did you clear only template cache or everything?
Try also manually deleting the cache folder for your site and see what happens.
If this doesn't help then you should check if eZ has some problems loading your override templates (permissions etc...). Try turning debug on and see if eZ complains about not being able to load some templates. Also turn on "List of used templates" in debug and see which templates are requested and which are loaded.
Hope some of this helps.
--
Nothing is impossible. Not if you can imagine it!