Make sure your versioning scheme will allow you to properly upgrade. Consider this example:
A new beta release of your package, mypackage-1.0-beta1-0ubuntu1. You've since gone out of beta into stable and you're ready to upload a new package mypackage-1.0-0ubuntu1, this will fail because -beta1 is actually greater than -0ubuntu1. You really wanted to use the ~beta1-0ubuntu1 version scheme instead.
Make sure to check versioning before uploading:
$ dpkg --compare-versions mypackage-1.0-beta1 gt mypackage-1.0-0ubuntu1
If the return is False then you know you've incorrectly versioned your package. Note if you run lintian like above this usually catches version errors like this.