A bit OT but are you paying for this or is it free if you have the unlimited data plan? On my previous phone, I had some plan where the VZ navigator was free.
You are correct. This is an issue between 4.5 and VZNav. If this is not reported to VZW in the right way, then engineers will never know. One of tow things need to happen, a fix to NAV or VZW will work with RIM for a 4.5 patch.
My suggestion would be folowing. Internally there is a form to report device issues. This form requires 2-3 devices that experience the same problem beofre it can be used. Since there seem to a coupleof folks here having this issue I recommend the following.
PM each other, the form used needs a detailed description of the problem, the ESN numbers for the devices affected, phone number and some other info I do not remember off the top of my head. This then gets submited to network for investigation