Any chance you can upload a photo of the rust on the cooking grates? Is the rust only at the welded junctions where the bars cross each other? It's most likely just surface rust, but it would be helpful to see what state they are actually in.
The naval jelly would probably remove the rust from them, but I'd be a little more hesitant on using an acid like this on the cooking grates.
Best of luck!
Chris