Most of the time, I'd go with a percentage of the deal. What that percentage is depends on what the deal is.
Sales? 5-10%, depending on which way the sale is going.
Introduction? Most of the people the fixer knows he doesn't want the players knowing directly, because then he can't take his cut of the sale, but my benchmark is 5-10% of the new contact's monthly lifestyle cost - more wealthy/important people are going to have a higher lifestyle cost, so the fixer is going to charge the PCs more to be introduced.
Service, on the other hand, is where the fixer can really make his mint - because PC says 'I have a Situation,' and the fixer gets to gauge a) what the problem is, b) how bad the PCs are going to be screwed, c) how much the PCs would be willing to pay in order to make the problem go away, d) how much the PCs CAN pay, and d) how tough it'll be for the fixer to make the problem disappear. Typically, I'd put this at 1,000 per year the PC would get for the problem, up to a general maximum of 20k - anything over that, and the fixer is probably not going to do anything, because it's so egregious / messy / whatever. (In fact, the PC might get a Notoriety just with that call.) If it's especially bad, the fixer just might burn the PC to the shadows, blacklisting them and making it insanely difficult for the PC to work for the next few months until they a) survive and b) get righteous again.