Okay, I have just learned yet another reason why Android makes me hate life. 

I assume this limitation is in place for two reasons:

1. encouraging developers to do releases more frequently with fewer changes
2. to not flood the play store with a wall of text

The rule of thumb is that some common languages, typically mentioned here is Spanish tends to require about 30% more characters than English.

In practice this means your 500 character allowance string should be no longer than roughly 375-380 characters if it is intended for translation. Two and a half tweets worth of characters is simply not enough to fit all of this: 

"* Complete redesign for tablets and phones\n* Notes can now be created, edited and deleted\n* Synchronization of notes to online server or an SD card\n* Note conflict resolution screen when different changes need to be merged\n* Ability to send and receive note files or text from any app\n* Added new preferences like default font size, sorting, auto-backup and many more\n* Updated all translations and added some new translations: bg, en-au, hr, is, jv, vi"

I think you might want to pair it down a bit, and highlight the features that are likely to matter to your users. 

1) Most importantly Tomdroid now does more than displaying notes which is I assume your number one feature request since forever. 
2) You now look utterly stunning on both phones and tablets
3) You do synchronization (handling merge conflict nicely is merely a part of doing this right so no special mention needed in the changelog)
4) You take data from anywhere and likewise hand it out like candy
5) You are configurable like a bad ass
6) Available in your language, and so many more.

You can then put up a nice page with screenshots and nice explanations of everything. If you provide the screenshots I will even write it for you. We can do a big announcement and PR splash when Tomdroid 0.8 (or 1.0 I don't know what the plan is here) hits the Play Store to show it off to the world.

So you could get away with something like:

"* Notes can now be created, edited and deleted\n* Completely redesigned for both tablets and phones\n* Sync your notes with compatible services or to your SD card\n* Send and receive note files or text from any app\n* More configurable than ever\n* Available in more languages than ever before\n\n And much more, for a complete list of changes please go to http://github.com/tomboy-notes/tomdroid/0.7.3" 

A mere 379 characters, which seems significantly less likely to pass 500 characters for any common translation. In fact a 30% increase would be 493 characters.

To test, here is a quick pass at the Danish translation for this:

"* Noter kan nu oprettes, redigeres og slettes\n* Fuldstændigt redesignet til både tablets og telefoner\n* Synkroniser dine noter med kompatible services eller til dit SD kort\n* Send og modtag note filer eller tekst fra enhver app\n* Flere konfigurationsmuligheder end nogensinde\n* Tilgængelig på flere sprog end nogensinde før\n\n Og meget mere, for en fuldstændig liste over ændringer gå venligst til http://github.com/tomboy-notes/tomdroid/0.7.3"

426 characters, a rough 12.5% increase.

So.. that is my recommendation. Suck as it might.