Are there any technical problems with renaming a plugin?

I have recently released a plugin called ‘SEO Image Galleries’ only to receive a call today from a #$*&@ SEO company called ‘SEO Image’ that is claiming trademark infringement because they have trademarked ‘SEO Image’.

If I were to rename the plugin will people still be able to get auto updates? I don’t want to risk losing all the folks who already installed it.

Thanks.

One other thought – I suppose even if that works, all the links pointing to the current repository page will no longer work?