Agreed.  The PCs are kind of stuck on this one.  The Liberals have run a very fiscally conservative government so there isn't much room for the PCs to maneuver.  Without some scandal or a change in plans by the governing Liberals the PCs will have  tough time making inroads.

As for the NDP, Nova Scotia tested the waters with them a few years ago and are, quite rightfully, not particularly eager to go back.  As with pretty much all NDP governments outside of Saskatchewan the Nova Scotia NDP were a bit of a disaster.