There might be something wrong with the tables handling styles/templates and whatnot. You could try backing up those tables (I think style and template are the relevant ones, but you should see if there are more style-related tables too), do a clean install of vBulletin and copy over those tables from there.

Edit: Oh, and just to be sure - you know other users are experiencing this too, and it's not just you?