If you have given the correct access and the problem still isn't resolved, but WordPress says that it is indeed modifying the file I think you should double check and make sure the rewrite_module is on. If you're site is live and you're having this problem you need to call your hosting service and they'll be able to help you. However, if you're local, I think I can help you :)
I once had this problem after I started trying out WAMP and I tried everything you stated above. Here's what I did: left click on the tray menu icon, go to Apache > Apache modules, then scroll down and make sure rewrite_module is checked. If it is not, check it. WAMP should then restart and (in theory) your problems should go away!
Good luck! Write back and let us know if it worked!