To me its pretty easy deal to fix.
I know both Reebok and the UFC have to agree on the sponsors but just sell 3 or 4 spots on the fighter kit apparel for one, two, or three years or whatever. Between the 3 or 4 sponsors shoot for another 10 to 12 million a year in the pot. With that you can easily double the current pay scale. Nobody would be bitching then as only a handful of fighters would really be getting less.
I also think(maybe they are doing this IDK) they should take in effect a fighters history outside of the promotion. Say Fedor comes in, you can't pay him 2.5K in sponsorship.