First of all, Ice cannot be compiled on Debian 3.0 (the latest
released version), since it lacks recent enough versions of both
Berkeley DB and Xerces-C++. You can find backport repositories for
the DB through
www.apt-get.org, but Xerces you'll have to build (or
possibly backport) yourself.
The reason for build failure on development versions (testing and
unstable) is Ice's fault, at least according to my understanding (I am
not involved in Berkeley DB development nor do I use it; this is based
just on reading the sources). The Freeze library uses the txn_*
functions in the DB, which are just wrappers in versions 4.0 and up,
and if the DB is configured with with-uniquename (as Debian does),
these wrapper functions do not exist. I have attached a patch that
replaces the txn_* calls with calls to the wrapped functions for DB
versions 4.0 and up (if the calls work also in 3.3, they should just
be replaced instead of conditionally compiled).