It could be possible, although it's highly doubtful. The moon doesn't go away during the new moon, it's just "in front" of the sun, so we can't see the light that is being reflected from earth. Furthermore, waterbenders can bend just fine when the moon is at a mere sliver, as seen in Korra book 1 episode 8 when she fights Tarrlok.
That said, the cycle of the moon does have a significant impact on waterbending. In Airbender, it was stated that bloodbenders can only do their magic when the moon is full (although this was contradicted in Korra), and waterbenders are known to be more powerful at night. So it's likely that a waterbender is at their weakest [at night] when the moon is new. Remember though, the only time we saw water benders lose their ability entirely was when Zhao killed the moon spirit Tui and the moon disappeared entirely.
I kind of wonder if waterbenders would lose their abilities in a lunar eclipse though, since firebenders lost theirs during a solar eclipse....
Iakompake101 wrote: If their bending gets all its power from the moon and at its peak when it's full, would they lose their ability to bend if it's a new moon?
It shoudn't be possible otherwise waterbenders shouldn't be able to bend at daytime (since the moon isn't visible). Their bending depends upon the moon, and thus they only lose it if the moon is gone. If there's a new moon, their waterbending would be weak, but not gone since the moon is there.