tag cloud searching not working

I am having trouble with wordpress’s native tag searching. I have the tag cloud show up at footer, when I click on one of the tag, I got a ‘Nothing found’ page, although I am pretty sure my posts are tagged.

I have tried to deactivated all the plugins, still now working. I am using default permalink. Can anyone help me?