Should I spray some flux on my board before putting it in the reflow oven?
The flux does evaporate and it can affect the solderabilty of the board. Typically there might not be enough wetting and the solder doesn't flow as well. 

However, I do my own prototyping and the larger boards sometimes take an entire day just to stuff all the parts. This leaves the flux on the board to evaporate for hours. We however do not have problems as you described above, I'm willing to bet that your temperature profile is not as hot as it needs to be. I would throw a thermocouple and see if you can measure it.

It probably wouldn't hurt to throw on additional flux on the board before you put it in the oven, I wouldn't spray it as this would leave a no-clean residue over the board. I would match what you get from your paste supplier and get the flux from them.

If you still have problems you might want to switch solders, I've never had a problem with kester solder flux. I have also been impressed by Qualitek  solders (not associated with them, just really like them and the price) but I have only used lead free.

Another thing you might want to consider is switching to a water soluble solder, which you simply clean of your board with a warm spray of deionizied water (assuming you don't have many components with a high moisture sensitivity level, or you can put those on afterwards)

As a recap, I'm willing to bet you need more heat, but you could just have bad solder flux in your paste. You can add flux, I've done that before, but the trade-off is residue and cleaning. You have many options to fix this problem, it really depends on what your components can tolerate.