does this problem has something to do
with Google App Engine Cloud
inrastructure
Yes.
The API method you're calling is rate-limited:
The default rate limit for calls to
the REST API is 150 requests per hour.
The REST API does account- and
IP-based rate limiting. Authenticated
API calls are charged to the
authenticating user's limit while
unauthenticated API calls are deducted
from the calling IP address'
allotment.
This works fine if your app has a dedicated IP; on App Engine, many applications will potentially use the same source IP for their urlfetch request, so unauthenticated requests to the Twitter API will all draw from the same quota.
I haven't tested this, but my understanding is that even for calls that don't require authentication, if you choose to authenticate your request it will be counted against your account quota instead of the shared IP quota.
Nick Johnson posted a tutorial on how to send authenticated API calls to Twitter from App Engine.