I think I wouldn't do it. Google has a clear policy about what you can put above the AdSense ads. I'd definately check it with Google before you put anything near the referrals.
There is no issue at all with google-referrals and telling your visitors to use them. I get a bit tired of saying this but it's very simple: google wants people to download firefox, so yes, you can tell people to download firefox. Same with all other google-referrals. (adsense, adwords, google-pack etc.) Google wants their advertisers to be happy. Happy advertisers only get clicks on ads from people who actually buy something on their site. So asking people to click is not OK with google - those people aren't likely to be interested in the buy.