Problem with pagination and spaces in URL

I’ve only just noticed this problem, and I’m certain it didn’t exist a few months ago! Perhaps it had something to do with a WP update or plugin.

Basically, I have a page which lists a load of excerpts depending on what the value of $_GET[‘category’] is.

Here is the query I am using:
<?php query_posts('post_type=company&meta_key=Category&meta_value=' . $_GET['category'] . '&orderby=title&order=ASC&paged=' . $paged); ?>

The problem occurs when $_GET[‘category’] consists of multiple words, such as “Web Design”. However, I am not using spaces in my hyperlinks, rather they are like so:
<li><a href="<?php bloginfo('url'); ?>/directory/?category=Web+Design">Web Design</a></li>

And this works fine when on the first page of results, however when I go to page 2, the URL in the address bar changes like so:
http://www.website.co.uk/directory/page/2/?category=WebDesign

Notice how the ‘+’ has disappeared between ‘Web’ and ‘Design’.

I cannot understand why this is happening however, because I am using the posts_nav_link() function like so:
<?php posts_nav_link(' ', '<li><img src="' . get_bloginfo('template_url') . '/image/paginate-prev.gif" alt="Previous Page" /></li>', '<li><img src="' . get_bloginfo('template_url') . '/image/paginate-next.gif" alt="Next Page" /></li>'); ?>

This gives me the correct link on the frontend. So if I hover over the ‘Next’ button, it is trying to take me to:
http://www.website.co.uk/directory/page/2/?category=Web+Design

Which is correct, but for some reason WP is just stripping that ‘+’ character out of the URL after the link has been clicked.

Does anyone have any ideas why it might be doing that? Maybe I should just try a fresh install and reconfiguring everything? Although that is only a last resort for me.