I am new to WordPress, but have had Google Ads working for quite a while on my Website http://ladymoor-gate.demon.co.uk . I too failed to get Google Ads working on WordPress UNTIL I took the advice to edit the sidebar.php file, and insert the Google Ads code there. You may need to experiment to get the ads in the correct place, but it only took me three goes with a text editor.
The Blog http://blog.lgf.homeip.net really belongs to my wife. I just like hacking webstuff – it seems to work, although I got Public Service Ads for a few minutes.
Good luck to all having this problem.