You can't auto-update, however as far as I'm aware nothing prevents you from notifying the user that a new version is available, within your app. For example you could contact a web server to find out what the latest version is, and compare that to a build number in your app bundle, then display an appropriate alert/notification to the user. Or, you could get fancy and use the 3.0 push notifications for this.
In theory the appstore app/itunes will do this anyway, but it's clear that a lot of users don't see that.
Another thing you can do using the method I outlined (that the app store won't do) is tell the users that a new version is available, what it does, and that it's waiting for apple.
Even simpler is just to embed an 'announcements' channel in your app somewhere. That lets you talk to your users without waiting for apple - you can tell them there is a new version on the way, etc. I do this with an app I'm beta testing - a button on the main screen shows announcements, which I pull from my server.
Maybe if enough app developers did this, apple would start turning the approvals around quicker. Or change the legalese to prevent it [assuming it doesn't already] :-)