That's odd. The Web Store hosts extensions as well as apps and themes.
What do you mean it was "not the appropriate place"?
As far as notifying your users, though... I can think of two
possibilities.
If the extension contained a link to a website that you have some
control over, you could put a notification there. You've probably
already thought of this, though.
Option 2: I literally concocted this scheme in my head just now. If
you could find out what the key of the extension is — the deployed
copy, what all of your users have installed — then this idea might
work. You could set the key of your extension (
http://code.google.com/
chrome/extensions/manifest.html#key) to be that same key, and then set
the autoupdate URL (
http://code.google.com/chrome/extensions/
autoupdate.html) to point to a privately hosted version of the
extension. Then upload this new copy to the Web Store. If it doesn't
reject it for having these changes, it will host your extension in the
same place as before, which is where all of your users' update_URLs
point to. When they grab the new version with the new URL, it will
begin pointing to the new, privately hosted copy. Hopefully.