I am running Yoast and all the titles are working fine except for Category, Tag, Taxonomy etc pages where I cannot get the title to change from the default: 'Category:' or 'Tag:' etc.
I have deactivated and reactivate every plugin but it did not work.
Under Taxonomy - Category - Title I have %%term_title%%page%% %%sep%% %%sitename%%
Under Taxonomy - Tags - Title I have %%term_title%%page%% %%sep%% %%sitename%%
And it shows like this %%term_title/ Surfing the Planet
Please find an example: http://www.surfingtheplanet.com/category/espana/