We noticed a small bug that required the app to be restarted after purchasing (or restoring) the iAd Remove In-App purchase. This has been corrected and published to the iTunes App Store and is awaiting approval.
If you are experiencing this issue, just shut down the app and restart after you have purchased or restored the iAd Removal In-App Purchase. This will force the iAd Removal to take effect.