The problem of many learners is that they take the rule about negation causing Genitive too far. It is not "Negation = Genitive". It's "Negated Accusative = Genitive". And because Accusative is so commonly used, people spread this too far. But actually any other case just stays the same when negated.