When this happens, try clicking on the 'use a new identity' button on Vidalia, and then resending the request.