I noticed that electropolishing makes a huge difference when it comes to solder printing. Ever since I noticed that I always order electropolished stencils, and never had a problem with them.
That said, if you solder paste is old, you can add a bit of no-clean or water-soluble tacky flux gel and stir it thoroughly. Another possibility is your paste was too cold - if it was stored in refrigerator, give it 2-3 hours to warm up before using, or use room temperature stable paste which - as name suggests - doesn't need refrigeration and can be stored at room temperature. If you are placing parts manually, I highly suggest you to use room temperature stable paste, as it doesn't dry up nearly as quickly as regular one does, so you will have plenty of time to place all parts. It's a bit more expensive than regular one, but it's absolutely worth it unless you have rather high volumes of boards and going through paste very quickly.
Also - thoroughly clean your stencil with isopropyl alcohol after each use, and especially before storing it, as solder balls that remain on a stencil can clog up small holes. This is especially so if you have small pads (like 0201, or small pitch BGAs) - this will save you major headaches next time you use it.