Thanks for your help guys we tried both of your methods but they didn't work. Eventually we managed to get it right after some more trial and error. Here's what ended up working for us.
RewriteEngine On
RewriteCond %{REQUEST_URI} ^/blog/$
RewriteCond %{QUERY_STRING} ^tag=([a-z]+)/page/([0-9]+)/$
RewriteRule ^(.*)$ http://example.co.uk/blog/?tag=%1&paged=%2 [R,L]
Note: The were just a few syntax errors that seems would work on an Apache PHP setup but needed tweaking for a CGI PHP setup.
We also re-used this htaccess code to account for categories too by changing 'tag' for 'cat' and changing the regular expression for the cat from letters to numbers:
RewriteCond %{REQUEST_URI} ^/blog/$
RewriteCond %{QUERY_STRING} ^cat=([0-9]+)/page/([0-9]+)/$
RewriteRule ^(.*)$ http://example.co.uk/blog/?cat=%1&paged=%2 [R,L]
Thanks again.
Hope this can help someone in future with the same issue.
Now on to the others! :)