Helping people with computers... one answer at a time.
Surprizingly, the answer is a resounding no. Change all the passwords you like, but your sysadmin may have left a way in. And it turns out to be a legitimate way in.
Because of the nature of the work, it's often the case that we give our system administrators an exceptional level of access to our systems. It's not uncommon for system administrators to need "root" (or total, unrestricted) access to your server in order to do their job.
Obviously if you've parted on less than amicable terms, you should make sure to scan your system for things like rootkits, additional accounts and other less than honorable "gifts" your former admin may have left behind.
Regardless of how you parted, there's also a legitmate technique for logging in that bypasses password authentication: SSH public key authentication. If your admin used it, and he or you didn't remove it, he may still have access no matter what the passwords are set to.
This technique uses public key cryptography to create a matching public and private key pair. The public key is installed on the server, and then possession of the private key is enough to log in. It's considered more secure than password authentication, because only trusted individuals can install the key on the server, and the matching private key is required to match in order to login. If you don't have the matching private key, you can't use this technique to login.
Thus to remove someone's access from a server, one must not only change account passwords, but also remove that user's public keys that may have been installed as well ... or disable public key authentication completely.
To disable public key authentication completely, on the server you'll need to modify the file /etc/ssh/sshd_config. Look for the line that says "#PubkeyAuthentication yes" (with, or without the leading "#"), and change it to "PubkeyAuthentication no". Or simply add a line saying "PubkeyAuthentication no". Now restart the sshd service. I'm being intentionally slightly vague here, because in reality someone that's already familiar with ssh should be making these changes. A mistake could lock everyone out of your server.
If you want to keep using public key authentication, which is understandible since it's quite handy, you'll need to remove your former admin's public key from all the accounts that it might have been placed in. To gain access, public keys are placed in the file "authorized_keys" in a subdirectory ".ssh" in each account's home directory. For example all the public keys listed in "/root/.ssh/authorized_keys" represent possible "root" logins. Similarly, public keys in "/home/admin/.ssh/authorized_keys" represent possible logins as "admin".
The solution is simple ... locate all authorized_keys files, and remove from them the public keys you do not recognize, or those that you do recognize as no longer being appropriate. Each is on a single line within the file, and legitimate ones will almost certainly have an identifying comment at the end.