Oops, didn't notice that earlier, but you shouldn't have sudo in there
That would produce an infinite loop, since it reads /etc/sudoers each time you run sudo ...
username ALL=NOPASSWD: sudo shutdown -P now
really should work.
username ALL = NOPASSWD: shutdown -P now
Also, note that the position in the file is important. From the man-page of sudoers:
When multiple entries match for a user, they are applied in order.
Where there are multiple matches, the last match is used (which is not
necessarily the most specific match).