Sarge also does not support tilde in versions (page 218)
More...Reported on: 2005-06-21
In chapter 5. The Debian package management system on page 218:
In the end of the forth paragraph, I claim that the woody tools do not support the tilde (~) character in the version number string. The sarge tools also do not support this character. Full support for the tilde character in version numbers will come with the release of Debian etch.
Update: while sarge's dpkg and even APT support the tilde character in version strings, the majority of package- and packaging-related tools in the sarge archive do not. Therefore, the tilde is not fully supported in sarge, but it is in the etch release.