Just an aside (I'd make this a comment but I think it will be slightly long)...
It feels very good for a programmer to be able to get a single conceptual operation on one line. To the programmer (at the time) it feels more readable, logical and just feels right.
It is almost never a good thing. For one thing, later it will be harder to parse than two lines--even if your gut reaction now is that it is more readable. Also--the more operations on one line, the harder it is to debug.
For readability, I'd say the Generics solution is about as much as I'd put on a single line--for the casting solution I'd break it down into two lines; I'd also break it down into multiple lines if either of the parameters were operations instead of just simple variables.
I know a lot of people won't agree with this and to tell you the truth I tend to put quite a bit on one line at first, but what I've noticed is that at the first sign of trouble or any confusion, it makes my life easier to break everything down into separate statements with clearly named variables.
At least as important--in cases with nested collections, I will often wrap the collections in a different object as well. This would be interesting in your case--the call would become a little more clear.
dataHolder.put(category, newKey, newVale);
Hides the mechanics of the nesting of the collections (which otherwise can be complex to remember correctly and easy to screw up) and makes your intent much clearer.
This pattern of wrapping (Not extending but encapsulating) nested collections feels strange at first but I really suggest you just give it a try--it really cleans up a LOT of code, makes everything much safer adds to everybody's comprehension, changes a "Collection" to a business object (where you can place business methods--a refactoring you will appreciate almost immediately), and just generally helps your code all over.