I think I found out what is wrong... It's all due to a limitation of my old Netgear DG834GV5 router, something about the ability to multicast between wifi and ethernet. Whatever that means.
I've tried plugging the cable in the notebook and the printer was right there waiting...
I hope this helps someone else!