That typically indicates incorrect or loose connections (or wrong chip!), or a chip set to use a crystal but no crystal present.
Use verbose upload to see what signature it's seeing - sometimes that's useful - ie, make sure it's not actually a 328-not-p instead of 328p,