brotherhood_of_LAN - 4:50 am on May 16, 2013 (gmt 0)
It's true you run the risk of being considered 'less trustworthy' when it appears you're selling links to boost another sites rankings, but it's effective... hence the ultimatum from the link buyer (though buyers would tend to prefer a link within content rather than tacked onto the top/side/bottom of a template).
It's really up to you whether you want to continue with the arrangement or not. You yourself can judge the risk/reward of loss of $ and/or a potential loss of search engine rankings.
If the buyer considers a nofollow link worthless or worth a lot less, consider charging more if you plan on keeping the link.