Make sure you do not modify the device token before providing it to Twilio. If using a command line tool make sure to url-encode the token.
Make sure that you are using a development certificate for a development application and a production certificate for a production application.
If you are using a traditional certificate, you can tell its environment by looking at the common name field
If you are using a universal certificate, you can use it for both development and production applications. However you have to make sure that you have properly indicated the type of application by setting the sandbox parameter when you create the credential. You can check the sandbox flag of your credential via the REST API.