What server behavior is running on the page? You shouldn't need an address until after you get back from the authorization for express checkout. It sounds like you might be trying to process your payment when you get this error, but it also sounds like you haven't actually gotten to the paypal web site yet.
That is why the error makes no sense, because the address should be set after they log in to paypal and not on the way. What server behaviors do you have applied to the page? What part of the process is giving this error? The solution is going to involve editing the Server Behavior related to the error, but I'm having a hard time figuring out exactly what is happenning so I don't know for sure.