For most of history, cattle were the primary form of wealth. This is a form of treasure that would be extremely annoying for PCs to deal with, and therefore should be exploited.
Let’s say that there is a people that exclusively uses cattle for wealth. Gold jewelry may be valued as a luxury good but is not used as currency. The PCs need to buy something from the king of this people.
To strike a deal with the king, the PCs will have to go to the nearest place that accepts gold, and buy a herd of cattle. They will then have to drive it to the king and enter negotiations.
I’d make the cattle drive a skill challenge. Besides nature checks, any smart decision made by the PCs (for instance, to hire experienced cattle drivers) would count as a success. More successes would mean that less cattle wandered away during the cattle drive.
Also, a lot of cattle-wealth cultures area also cattle-stealing cultures (highland Scots for instance). Therefore, there would be a few combat encounters on the way to the king; raiders whose intent was not to kill the PCs but to distract them long enough to panic the herd and make off with a few cows.
When the PCs meet the king, he’d say something like “My spies inform me that you lost x% of your cattle on your way.” He’d judge the PCs accordingly. If the PCs had done a bad job, he’d be more likely to think the PCs were weak and steal the rest of the cattle himself.