Procedure is ok, we had some cases with nuvi 1350, solved with a software update from Garmin. you can read that thread:
[Only registered and activated users can see links. ]
No idea about your problem sorry. May be you can try to downgrade to an old 34xx sw version, clear NV and then upgrade again.
Reverting to an old sw can solve some problems sometimes.