I've been getting quite a few messages about this "400: Bad Request" error people are seeing when trying to reference the Virtual Earth Web Service, more specifically when trying to fetch tokens so it's worth posting a little something on how to fix it. Specifically, the error is, "There was an error downloading 'http://staging.common.virtualearth.net/find-30/common.asmx'. The request failed with HTTP status 400: Bad Request."
The current documentation in the SDK shows a reference to https://staging.common.virtualearth.net/find-30/common.asmx; however, users aren't getting the WSDL downloaded (I've had this problem myself). So, the solution is to change the reference to https://staging.common.virtualearth.net/find-30/common.asmx?wsdl.
In Visual Studio 2008, you'll need to take a (odd) extra step. For some reason adding a Web Reference is different when you go to the "Add Service" advanced options than if you were to just Add Web Reference from Website menu. So, in Visual Studio 2008...
This should fix your issues. We'll be updating the SDK soon too.