I've seen other apps do this before, so I don't think it would be a problem... but if someone searches for your app by name that could be a problem. If this is a paid app, the following won't be all that useful, but if not you could possibly leave a tombstone that points to your new app temporarily; in effect another app that does a market search for the new one. At least this way if someone is searching for the old app they will find a pointer to the new one.
This makes upgrade scenarios a little ugly, but it may help you retain users.
From: firstname.lastname@example.org [mailto:email@example.com] On Behalf Of Peter Jeffe
Sent: Sunday, December 13, 2009 11:32 AM
To: Android Developers
Subject: [android-developers] application name change
We're having to change our app's name due to it being somewhat close
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.