I use KeePass for storing my passwords, ok.
What should I use if I want to store my several hundred contacts (name, phone number, email, etc.) encrypted?
p.s.: under Linux/BSD
You can try to create an encrypted virtual disk. For example truecrypt provides a way to create encrypted files that can be used as storage. (All you need is to mount the file once with the pass and you can use it like any storage place, then unmount and it's secured)
Or else you can also crypt/uncrypt an archive file with GnuPG but that will be more a burden to decrypt everytime you want to access it then recrypt it etc.