Note that because 3.5.0-39 was installed using the *old* version of apt, it's actually expected that this version of the kernel won't be marked for autoremoval. 3.5.0-40 is the first version that will be a candidate for autoremoval, and it won't actually be autoremoved in this case because you rebooted to 3.5.0-40 before installing 3.5.0-41... making 3.5.0-40 the "last good" kernel that's being kept.
Note that because 3.5.0-39 was installed using the *old* version of apt, it's actually expected that this version of the kernel won't be marked for autoremoval. 3.5.0-40 is the first version that will be a candidate for autoremoval, and it won't actually be autoremoved in this case because you rebooted to 3.5.0-40 before installing 3.5.0-41... making 3.5.0-40 the "last good" kernel that's being kept.