There's a saying that sums this up well:
"An oral contract is as good as the paper it's written on."
Basically, enforcement of that contract is going to be tough. There is one thing you can fall back on though: The discipline of constant dealings. You said you had witnesses to this agreement. That's good, that makes it more than his word against yours. Using the discipline of constant dealings, you can tell him that since he is not going to hold up his end of the bargain, you're not going to ever deal with him again. You're also going to tell the witnesses to the agreement that he reneged on it, and they will cease dealings with him as well.
Now, this might encourage him to play fair and pay up, or it might not. But if it doesn't, he's hurting himself more than he is hurting you.
Taking one for the team.
Being the first to trust someone who has no trust established.
Those with an established reputation for fair dealing have more to lose by violating it as well as a history of not doing so.
"Good Will" is an asset.
Lex Mercatoria is the free-market mechanism by which these situations were self governed in ungoverned areas.
http://en.wikipedia.org/wiki/Lex_mercatoria