Passwords in databases are rarely encrypted, they're hashed instead. Encryption is a reversible process - you can decrypt content, given that you know the encryption method and password. Hashing on the other hand, isn't a reversible process.
What you're looking at is not an encrypted password, but a hashed one.
On the question of replacing the password in your database - this is easy to do, you'll just need to use the same hashing algorithm, generate your own hashed entry, and store it in the database. Keep in mind also the fact that most hashing algorithms use salt.
I'd suggest posting the product name, or the system you're trying to change the passwords for, then we may be able to let you know how to change these passwords.
One thing is certain - it would be really hard to find out the original passwords from the hash (unless there's no salt, or something that exists in rainbow tables).
I've looked at it, it's most definitely a base64 encoded hash, the hash algorithm most probably being MD5 or similar. What you're doing wrong in your decoding is that you're trying to make sense of text data (which looks like garbage text and doesn't make sense), while you've got to look at the ASCII codes of each character instead. Look at the last text output field of http://www.hcidata.info/base64.htm
You'll see 16 bytes (or 8 bytes) of ASCII hex codes. This is your target. Then look at the output generated by the various hashing algorithms: