[Markus Heinsohn]

Sometimes fictional leagues will enter tough times financially, but over a few seasons this will even out and correct itself and players adjust their demands to what the market can offer...

The payroll can indeed be higher than the budget occasionally, for example when players receive high contracts through arbitration or when the market size drops and the owner adjusts his budget.

In your case, trades would work if the players you offer have a lower salary than the players you receive. However, your owner would probably not allow this if you don't have budget room yourself... so, it is working as intended really.