If you are using Express Checkout, then the shipping address they enter on your site can be overridden by the paypal checkout. That might be what happened. If you need help debugging, please contact me via Skype and I'll debug it with you in a screen sharing session.