This problem is not related to the position of the ads, it is related to the nature of the website. When a person comes to a wallpaper website, he just wants to LOOK at the pictures or Download the pictures. Well, I think the best thing you can do is changing some big policies in your websites. But policies, I mean big plans, maybe you should give a short description or some articles about each wallpaper and make your visitors to comment on the wallpapers, then some of the interested people will look at the comments and read those comments and they possibily click on the adsense ads too. Remember that Adsense can detect relevant texts, it cannot detect pictures. I mean when an Elvis Presley fan come to your website to take a wallpaper of elvis, there is no information about Elvis on the adsense ads. so Your visitors are not interested in those non irrelevant ads. They are just annoying to them.
Try adding relevant images next to, or above, the ads. That should increase your CTR at least 500% instantly.