Parent category permalinks not working correctly

Hi,

On http://wonderfulwanderings.com I have categories for countries and cities within those countries.

My permalinks are setup to display category pages as mysite.com/category/nameofthecategory
An example: for the category ‘Barcelona’, the permalink is http://wonderfulwanderings.com/category/spain/barcelona/

Now, this works for most of my categories, but I have noticed that some still get the ugly ‘/?cat=’a number’’ permalink, like this one for Lisbon: http://wonderfulwanderings.com/?cat=193

I’ve gone through all my category links and when I listed them (list below) I noticed that all the once showing an ugly permalink are parent categories.

As soon as a category gets a child category, the permalink is ugly. I find this especially weird because when I go to the child categories, the link also displays the parent and there it looks good, like ‘spain’ in http://wonderfulwanderings.com/category/spain/barcelona/

Any idea why this may be?

To be specific, the ones that aren’t showing the pretty permalink are:
http://wonderfulwanderings.com/?cat=5 (USA)
http://wonderfulwanderings.com/?cat=70 (UK)
http://wonderfulwanderings.com/?cat=4 (Spain)
http://wonderfulwanderings.com/?cat=147 (Portugal)
http://wonderfulwanderings.com/?cat=106 (Netherlands)
http://wonderfulwanderings.com/?cat=165 (Mexico)
http://wonderfulwanderings.com/?cat=89 (Luxembourg)
http://wonderfulwanderings.com/?cat=48 (Los Angeles)
http://wonderfulwanderings.com/?cat=193 (Lisbon)
http://wonderfulwanderings.com/?cat=126 (Italy)
http://wonderfulwanderings.com/?cat=92 (Greece)
http://wonderfulwanderings.com/?cat=7 (Germany)
http://wonderfulwanderings.com/?cat=6( (France)
http://wonderfulwanderings.com/?cat=108 (Egypt)
http://wonderfulwanderings.com/?cat=8 (Belgium)

Thanks

PS not sure if this is Yoast or simply WordPress, so posting this in both forums

http://wordpress.org/plugins/wordpress-seo/