Which client are you using (LimeWire, BearShare, Phex etc)?

If you're using LW, first thing to try is this: In LW go tools > options > searching > basic & check whether the 'show license warning' box is ticked. If it does, untick it > Apply > ok...see if that makes any difference.

If you're still stuck, delete LW's preferences folder when LW's properly closed. See point 3 here & also point 2 if you've used older versions of LW in the past (there could be a folder in either location).
Fixes for LimeWire
This will kill all of your settings within options, you'll have to go back through afterwards & reset things. If you're not sure of your settings, go through LW's tools > options & write them all down, so that you can reset things later.
In case you're using Vista: LimeWire Pref Folder in Vista

Because this will revert all of your options settings back to default, the host that you've blocked won't be blocked anymore! If you want to try blocking that address again, write down the host's details before you delete the prefs folder