Was your phone originally a koodo phone? If not you may need to dial your own number instead of pressing and holding the one.
The reason being that your phones message Center may still be programmed for the original carrier.
Let me guess: when you try calling vm it asks you for the mailbox number you are trying to reach? If so, this means your phone is programmed with the wrong vm access number. You'll need to contact tech support to find out the correct one to use.