I had that problem myself. I just double-checked the notification settings in K-9 and rebooted, problem was fixed.
in the main screen in K-9. Press Menu key >>> More>>> Settings >> Account settings >> Notifications >>> then make sure the "New mail Notifications" box is check marked and so on and so forth in that screen. Also, you can try Pressing "refresh" when at the main screen in K-9