Stratix II PLL will not lock!?

The PLL's require quite clean supplies. What IO standard are you using for your regular IO? If you have left it as default, its probably 3.3v LVTTL which is about 20mA as standard which is too high in my opinion. If you have loads of IO all changing state at the same time you could get SSN (Simultaneous Switching Noise) which causes noise on the supplies and GND.

If you are using 3.3v LVTTL, I would recommend trying LVCMOS 3.3v and set the current strength to 4mA instead which is more than enough for point to point signalling. I doubt you would ever need more than 8mA when using 3.3v LVCMOS.

What is your PSU decoupling like? you could measure the PLL locked OP of the pll with a scope, and simultaneously measure the PLL supply. trigger off the PLL OP and if the two edges tie up, then bingo, you know your PSU is too noisy.

Hope this gives you something to think about.