Hi,
Is your account whitelisted to use the BudgetOrderService? One reason you could get this error is that you are unauthorized to use this service unless you are whitelisted.
If you are whitelisted for this service, could you please send me your SOAP XML request and response through Reply privately to author, so I could take a further look?
If you are not whitelisted and would like to be, please contact your Google representative about using this service.
Regards,
Anthony
AdWords API Team