I noticed that the non SEF url has a space inbetween as well. Do you know which file do I need to change to fix this?

The only files I've edited to make the tags work were the ones mentioned above - it's worked for me several times. It's possible there's something unique to your setup that's causing the issue. Sorry I can't be more help.

Aww, k thanks anyway.

Woot solved it!

Just needed to fix case 'tag'

case 'tag':
$tag=str_replace('%20','-',$tag);
$tag=str_replace('+','-',$tag);
$title[] = $tag;
break;

in components/com_k2/sef_ext