The record can exist and it might be a breach of someone's fundamental right to privacy to make that record available via data processing.
The ruling did not state that the record will not cease to exist or would not be accessible, but that data processing of the information could be a breach of the person's right to privacy.
Another example: Let's say Bob actually only did commit a very minor crime. In the EU the ability to rehabilitate is protected by law. Only certain government departments have the right to access certain classes of crimes on a criminal record after n years.
If you were to make a database of court judgements (nearly all of which are a public record of fact), and make available Bob's criminal record after n years had passed. You would definitely be in breach of the law.
This has existed in law for a long time and isn't completely illogical.
Read the ruling, it acknowledges records of fact and states that the right to process those records doesn't trump the fundamental rights.
It's why they're called fundamental rights and data processing isn't on that list of fundamental rights.