I encountered this problem while using Visual Studio's Git integration to manage the project. For some reason the Windows Phone 8 project would compile just fine when targeting x86, but when I set it to target ARM, it would fail compiling with an error indicating that "Advertising" didn't exist in the Microsoft namespace.
I ended up resolving the issue by removing the Microsoft.Advertising.*.dll reference and adding it again.