They could have simply left the old library, deprecated it, and added in their genericed one as a a new package. It had to be modified anyway.
Type assertions have no ability to recurse. RN you assert both classes are a UTF8 value in the constant pool. Or really 1 class is a UTF8 value, which the compiler know the first one is.
But with Generics, you may not know what it holds at runtime so this doesn't work. You'd have to constantly rebuild the constant pool (Slow) each time a new _kind_ of generic is used.
So either a new type+byte code would have to be introduced, or the type assertion instruction would have to become recursive. The later is a breaking change.
Also interfaces break this b/c those are class specific. So a Lorg/my/company/myClass$5; and Lorg/your/company/yourClass$0 might both implement the same interface. But that interface information isn't in the collection class, but those to class's class files. So really it just needs new byte code.
My understanding of generic type erasure is that it is more of a language issue than a VM issue. Nothing in the VM prevents reified generics, but when generics were introduced in Java 5 they decided to use type erasure in order to avoid having to produce a whole new collections standard library or break compatibility with existing code.