I also have a cheap development kit based on the same part EP2C5T144C8, and I tried to compile a simple project with few stuffs (CPU/JTAG/UART/PIO/CLK/...) and compilation resulted in an error of insufficient M4K blocks to fit within, having exceeded in 115%, what means that total memory blocks required were 30 ( just 4 units more than available on core ). I used the Quartus2 revision 13.0, the last one which supports the Cyclone II family.
The only reason that I can guess to explain the divergence on resources required not matching the 50 M4K blocks informed on product specifications is that I used the Web edition along with the economic variant /e of the core. It is clear that this core in particular is not suited to work with the Nios2 core, unless for very limited applications.