I tried again on an ubuntu 6.10 system, and I get the same error. When I installed I ran:

sudo strace -f -o /tmp/strace.txt -s 1024 apt-get install samba

and in the output I see this (edited slightly to remove long strings):

11388 stat64("/var/lib/samba/passdb.tdb", 0xbff1f12c) = -1 ENOENT (No such file or directory)
...
11395 open("/var/lib/samba/passdb.tdb", O_RDWR|O_CREAT|O_LARGEFILE, 0600) = 8
11395 fcntl64(8, F_SETLKW64, {type=F_WRLCK, whence=SEEK_SET, start=0, len=1}, 0xbfefede4) = 0
11395 read(8, "", 168)                  = 0
11395 _llseek(8, 0, [0], SEEK_SET)      = 0
11395 ftruncate64(8, 0)                 = 0
11395 write(8, "TDB file\n\0\0"..., 696) = 696
...
11395 open("/var/lib/samba/passdb.tdb", O_RDWR|O_CREAT|O_LARGEFILE, 0600) = 8
11395 fcntl64(8, F_SETLKW64, {type=F_WRLCK, whence=SEEK_SET, start=0, len=1}, 0xbfefede4) = 0
11395 read(8, "", 168)                  = 0
11395 _llseek(8, 0, [0], SEEK_SET)      = 0
11395 ftruncate64(8, 0)                 = 0
11395 write(8, "TDB file\n\0\0\0\0\0"..., 696) = 696
11395 fstat64(8, {st_mode=S_IFREG|0600, st_size=696, ...}) = 0
11395 mmap2(NULL, 696, PROT_READ|PROT_WRITE, MAP_SHARED, 8, 0) = 0xb7a8d000
11395 fcntl64(8, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=0, len=1}, 0xbfefede4) = 0
11395 fcntl64(8, F_SETLKW64, {type=F_RDLCK, whence=SEEK_SET, start=580, len=1}, 0xbfefedc4) = 0
11395 fcntl64(8, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=580, len=1}, 0xbfefedc4) = 0
11395 write(1, "TDBSAM version too old (0), trying to convert it.\n", 50) = 50

so it appears that the file /var/lib/samba/passdb.tdb is first created, then there are complaints that it is too old, and then it is converted. This isn't directly related to the problem reported about account_policy_get, but still seems a bit odd.

The account_policy_get errors look like this:

11395 open("/var/lib/samba/account_policy.tdb", O_RDWR|O_CREAT|O_LARGEFILE, 0600) = 9
11395 fcntl64(9, F_SETLKW64, {type=F_WRLCK, whence=SEEK_SET, start=0, len=1}, 0xbfefe894) = 0
11395 read(9, "", 168)                  = 0
11395 _llseek(9, 0, [0], SEEK_SET)      = 0
11395 ftruncate64(9, 0)                 = 0
11395 write(9, "TDB file\n\0\0\0\0\0\0\0"..., 696) = 696
...
11395 mmap2(NULL, 8192, PROT_READ|PROT_WRITE, MAP_SHARED, 9, 0) = 0xb7a8a000
11395 fcntl64(9, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=164, len=1}, 0xbfefe3d4) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_RDLCK, whence=SEEK_SET, start=420, len=1}, 0xbfefe734) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=420, len=1}, 0xbfefe734) = 0
11395 write(1, "account_policy_get: tdb_fetch_uint32 failed for field 1 (min password length), returning 0\n", 91) = 91
11395 fcntl64(9, F_SETLKW64, {type=F_WRLCK, whence=SEEK_SET, start=420, len=1}, 0xbfefe724) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_WRLCK, whence=SEEK_SET, start=164, len=1}, 0xbfefe294) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=164, len=1}, 0xbfefe294) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=420, len=1}, 0xbfefe724) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_RDLCK, whence=SEEK_SET, start=376, len=1}, 0xbfefe734) = 0
11395 fcntl64(9, F_SETLKW64, {type=F_UNLCK, whence=SEEK_SET, start=376, len=1}, 0xbfefe734) = 0
11395 write(1, "account_policy_get: tdb_fetch_uint32 failed for field 2 (password history), returning 0\n", 88) = 88
...
and so on.

So it appears this file is also created, and then there are errors using it. Seems odd to me.

Is there anything else you need?