After some debugging I found the issue.
The main problem is that HttpUtility.UrlEncode() transforms "Hello World" to "Hello+World", and if we have more than 100 twits the query that comes back from the request is "Hello%2bWorld".Transform that to "Hello+World" and everything comes ok.
So basically you have to be very careful with the URL Encoding.