I just checked all the example designs for the latest release (Nios II 1.0 SP1) and the PLL frequencies all match the system clock listed in SOPC Builder for that project. If they somehow got changed in your examples, it is incorrect. The PLL and SOPC Builder frequencies should match. Note that the fast design targeting the 1S40 board runs at 138MHz while the same design targeting the 1S10 runs at 120MHz. Perhaps this is the difference you noticed.
The reason the full_featured example design has been set to a lower frequency than the fast design is that the full_featured design contains far more peripherals, which usually degrades the maximum frequency a system can run. In general, all other variables being the same, the more logic you add to a system, the slower it's maximum frequency will be.
Hope that helps,
-Nate