In theory, they can. This happened in 1965 where after the fall of the Marijnen Cabinet, a centre-right coalition (KVP, ARP, CHU, VVD) a centre-left coalition was formed instead (KVP, ARP, PvdA). This was done because multiple parties believed new elections would focus on the introduction of commercial television, which also caused the collapse of the previous coalition.
However, restarts were already relatively rare (only four times since 1900), and this particular one was somewhat controversial, given the switch from right to left without voter input, something which also resulted in the formation of the party D66 at least partially in response to this.
This eventually created a convention that after a cabinet collapsed a snap election is required, to gain new input from the electorate.
In this case, trying to form a new cabinet would have likely been highly controversial, given that current parliament composition would likely require working together with PvdA-GL, a left-wing party. Meanwhile, as for renegotiating the cabinet, this would have the issue that the original issues still persist.
Also, for renegotiation, to some extent the reason the cabinet failed was actually a refusal from parties to renegotiate. In this case the PVV wanted the other parties to commit to a series of policy points against immigration, which had already been rejected and negotiated differently during the coalition formation. Meaning it was in essence an attempt to force renegotiation or having the cabinet fall.
So, to summarize, forming a new cabinet is legal, but against long-standing convention (which in parliamentary politics can carry at least as much weight as the law), and practically speaking it wasn't possible anyway, given ideological conflicts with alternate options.