Yep, not sure switching to another PPC program would be the answer. You may want to check out some "heat map" diagrams to see if ad placement may be an issue, for example.
But just for information sake, if you're looking for another PPC-type program, one that comes to mind is
BidVertiser.
Many of the terms are similar. I've advertised with them, but haven't yet worked with them as a publisher, so I don't know how well it goes on that end.
One difference is (last I knew, unless this has changed since then), the code they give you to place on your site is only for the site they approve, which unlike Adsense, you can't go placing that code across other sites they haven't approved yet.
And Bidvertiser runs text-only ads (no graphics, category, videos, etc).