My blog was set as homepage and caused the same issue: all of the tags links would come out as 404

Here is how I fixed it:

BlogEntry.php

'Link' => $this->getParent()->Link() . 'tag/' . urlencode($tag)
changed to:

'Link' => $this->getParent()->Link() . 'home/tag/' . urlencode($tag)

In TagCloudWidget.php
"Link" => $blogHolder->Link() . 'tag/' . urlencode($tag)

changed to
"Link" => $blogHolder->Link() . 'home/tag/' . urlencode($tag)

where "home" is the page name of startpage i.e. the blog

@3 midgets In a man suit
I can see that it would work on your site, too:

http://2branson.com/tag/don+solice

http://2branson.com/home/tag/don+solice

thanks Filtre_ just what I was looking for... I had noticed that adding the home to the url worked, but had not a chance to look into the code.. you have saved me some time ;)

any outstanding issues once this change is made?

[Updated]
Ok, after some messing, I have found that it seems better to create a redirector page that is labelled as home (not shown in menu) that redirects to your blog page.
This way I haven't needed to edit any of the widgets as show previously.
Not sure if I will suffer any performance loss due to the redirect, but for my purposes this seems to be the more manageable solution.