That icon is mandatory. Android market won’t let you update your app without it.
Also they’ve enabled the inclusion of a high-res feature graphic (1024 x 500) and a link to a youtube video of your choice.
I don’t think a 512×512 icon will be of any use on a mobile phone, but Google TV springs into mind.
Still, 512 x 512 is like a proper resolution cd cover image, so I’m guessing some sort of coverflow-like interface, or maybe just a grid where selected square zooms into full res.
At about 8k+ downloads now for Theseus Lite so I can taste that 10k milestone.
The latest update tried to address some user complaints and then my own complaints about lack of sales.
Lately the #1 comment seems to be the fast increasing difficulty, so I added 10 new super easy levels. Well they’re super easy for me but I’ve played this game quite a bit. I guess new users really need a nice soft landing into the more challenging levels.
The lack of sales issue I tried address by revamping the in-game ad for the full version, lowering the price to $2.55 and linking straight to the games detail page instead of a market search page (I didn’t know this was possible before).
Lastly I added admob ads into the level selection screen. Hopefully this will generate some much needed income (I already made like a dollar, wohoo) and drive more ppl to buy the full version to get rid of it.
Hello,
We’re writing to inform you about some changes to Android Market that require your attention.
Effective today, developers from 20 additional countries (Argentina, Australia, Belgium, Brazil, Canada, Denmark, Finland, Hong Kong, Ireland, Israel, Mexico, New Zealand, Norway, Portugal, Russia, Singapore, South Korea, Sweden, Switzerland and Taiwan) can now sell paid apps on Android Market. Over the next 2 weeks, users from 18 new countries (Argentina, Brazil, Belgium, Czech Republic, Denmark, Finland, Hong Kong, India, Ireland, Israel, Mexico, Norway, Poland, Portugal, Russia, Singapore, Sweden, and Taiwan) will be able to purchase paid apps from Android Market.
Please see the related post at Android Developer Blog here:
http://android-developers.blogspot.com/
We encourage you to visit the Android Market developer console at http://market.android.com/publish to make the necessary adjustments.
Thanks, and we look forward to continue working with you on Android Market.
Sincerely,
The Android Market Team
I received the email below the line yesterday.
Could it be? Could they finally be adding Finland as a country where you can buy and sell on Android market?
—-
Hello,
We’re writing to inform you about some changes to Android Market that require your attention.
Over the next few weeks, we’ll be adding paid apps support for additional countries. If you have selected to publish your paid apps to all locations and intend to support all new locations as we expand the number of supported countries for paid apps, you don’t have to do anything. If you have selected to publish your paid apps to all locations but intend to only target the currently supported 14 countries, please update your location selections to target these specific countries.
Please look for follow-up emails when we introduce paid apps support for specific additional countries in the coming weeks. At that time, you’ll have the option to target these specific countries.
Thanks, and we look forward to continue working with you on Android
Market.
Sincerely,
The Android Market Team
So it turned out the game crashes when you solve the last level in the lite version. Probably not what users wanted as a grand prize when they solved the levels 
I made the lite version of the game in a hurry and made a few ugly hacks to get a “Get the full version” item into the level selection list. Now it came back and bit me in the ass.
Fixed it, made an update, got into the just-in again, got ~1k downloads over night.
I still have one crash report which is really obscure, but I’ll save that for next week.
Just updated Theseus, which made the download count bounce from 1.35k to 2k in 2 days. It was down to ~10 downloads a day before this.
So if you wait a bit over a week and update your app you get back in to the “Just In” list; which gives your app considerable visibility in Android Market.
Some people seem to abuse this. The top developer according to androlib’s stats has 200+ apps which are updated continuously, doubtfully containing anything new. http://uk.androlib.com/scoreboard.aspx?board=topdevdownload