Delete your debug certificate under ~/.android/debug.keystore on Linux and Mac OS X; the directory is something like %USERPROFILE%/.androidon Windows.
The Eclipse plugin should then generate a new certificate when you next try to build a debug package. You may need to clean and then build to generate the certificate.