Power Saving ATmega644P

Let's start a checklist

  1. No floating pins.

Seems likely you have done that.

  1. Does the current drop when you turn off the ADC, what was it before turning off the ADC?

This seems like the problem area. Could the reference be damaged? is AREF bypassed with .1uF and nothing else connected to it?

  1. BDO sleep. Well, that is JFM so I can't help.

On a 1284p I have used the blank (factory default) had about 3mA with 5V, internal oscillator at 1MHz, ADC reference on, pins floating. When I set it to run a 16MHz crystal with full swing fuse setting, ADC ref on, and most pins floating I recall that it used about 18mA. I got different readings with floating pins from one microcontroller to the next, but that is expected.