I've just uploaded aptitude 0.3.4 to experimental. At this point all of the destabilizing changes I wanted to squeeze into 0.4 have made it into the source tree and seem to work, so this is a release candidate for 0.4 once the translators catch up. Please go test it!
Relative to the version in unstable, this version has UTF-8 support, a new dependency resolution algorithm, threading (e.g., the program is responsive while a download is going on), and a whole bunch of smaller bugfixes and new features (including some of the most annoying bugs in previous versions).
[UPDATE] I was just reminded that not everyone is familiar with how packages get into our archive. Packages don't go into the archive immediately upon being uploaded (which is why installing aptitude directly from experimental doesn't work yet); they first have to sit in an "incoming" queue until the once-a-day archive maintenance script runs and moves them into the archive.
In brief, aptitude will be available in the usual way at around 4-5PM EDT tomorrow, or you can get it from the following URLs (which will be removed around 3PM EDT tomorrow):
Comment byat 5:50 PM:
This post has been removed by a blog administrator.
Comment by Kevin Mark at 10:09 PM:
Hi Daniel, check out my diagram on 'how things get into debian'. Any comments welcome. It shows why things go into 'incoming' (that is if you can read it x-) ) -Kev   http://debian.home.pipeline.com/ , see 'current debian diagram'  firstname.lastname@example.org