http://www.altera.com/literature/an/an446.pdf
The app note for the Nios II plugin says it's not supported with Incremental Compilation, probably for the reason you've encountered. I suspect it's adding post-fit taps and not pre-synthesis taps. It should provide a way for you to select the tap type.
Incremental SignalTap II support in Quartus II changed in the 7.2 release. Before, you could insert incremental or non-incremental logic analyzers. Non-incremental analyzers were added after Analysis & Elaboration and could only tap pre-synthesis nodes. Incremental analyzers were added during Partition Merge and could only tap post-fitting nodes.
In 7.2+, the concept of incremental and non-incremental analyzers isn't distinguished by the SignalTap II GUI. Rather, Quartus II adds analyzers incrementally or non-incrementally depending on your Incremental Compilation setting. In Incremental Compilation, a single logic analyzer may tap both pre-synthesis and post-fitting taps, but you need to tap them in the correct order. Post-fit taps may require a second compile to tap correctly.