Debian won’t shut down completely

My Debian wheezy (64-bit) won't fully shut down. What I mean by this is that when I select "Shut Down..." from the menu the screen goes blank but the power button remains lit and front fan keeps working. Only after I hold down the power button for a 5 sec or so it actually shuts down fully…

Did some googling and usually power managment is blamed in these kind of situations. Here are some suspicious messages related to power managment in my /var/log/messages, in order of appearance:

kernel: [    0.000000] ACPI Warning: FADT (revision 5) is longer than ACPI 2.0 version, truncating length 268 to 244 (20110623/tbfadt-288)
kernel: [    0.010862] x2apic not enabled, IRQ remapping init failed
kernel: [    0.485956] ACPI FADT declares the system doesn't support PCIe ASPM, so disable it
kernel: [    0.494932] [Firmware Bug]: ACPI: BIOS _OSI(Linux) query ignored
kernel: [    0.546125] PCI: Using host bridge windows from ACPI; if necessary, use "pci=nocrs" and report a bug
kernel: [    0.747176] ERST: Table is not found!
kernel: [    0.747177] GHES: HEST is not enabled!

then there is few like the following two:

kernel: [    1.361930] ACPI Error: [DSSP] Namespace lookup failure, AE_NOT_FOUND (20110623/psargs-359)
kernel: [    1.361934] ACPI Error: Method parse/execution failed [\_SB_.PCI0.SAT0.SPT0._GTF] (Node ffff88040f4b5290), AE_NOT_FOUND (20110623/psparse-536)

There is nothing in the kern.log or syslog that relates to shutdown (in the kern.log there is point which I can identify as startup but messages preceding that point aren't related to shutdown. syslog doesn't seem to have any intresting messages at all). Here is the few messages from messages at the time I did last restart (early this morning):

Jul  3 01:03:49 shutdown[22028]: shutting down for system halt
Jul  3 01:04:49 kernel: imklog 5.8.11, log source = /proc/kmsg started.
Jul  3 01:04:49 rsyslogd: [origin software="rsyslogd" swVersion="5.8.11" x-pid="2537" x-info="http://www.rsyslog.com"] start
Jul  3 01:04:49 kernel: [    0.000000] Initializing cgroup subsys cpuset
Jul  3 01:04:49 kernel: [    0.000000] Initializing cgroup subsys cpu
Jul  3 01:04:49 kernel: [    0.000000] Linux version 3.2.0-4-amd64 (debian-kernel@lists.debian.org) (gcc version 4.6.3 (Debian 4.6.3-14) ) #1 SMP Debian 3.2.57-3+deb7u2
Jul  3 01:04:49 kernel: [    0.000000] Command line: BOOT_IMAGE=/boot/vmlinuz-3.2.0-4-amd64 root=UUID=751d0e52-b064-4503-be7c-11270f8089e3 ro quiet

When executing shutdown -h now in the root terminal the result is the same (not full shutdown) but there is more info in the syslog:

Jul 3 14:58:04 shutdown[3929]: shutting down for system halt
Jul 3 14:58:04 init: Switching to runlevel: 0
Jul 3 14:58:05 minissdpd[3235]: received signal 15, good-bye
Jul 3 14:58:05 bluetoothd[3057]: Terminating
Jul 3 14:58:05 avahi-daemon[3055]: Got SIGTERM, quitting.
Jul 3 14:58:05 avahi-daemon[3055]: Leaving mDNS multicast group on interface eth0.IPv6 with address fe80::beee:7bff:fe74:647d.
Jul 3 14:58:05 avahi-daemon[3055]: Leaving mDNS multicast group on interface eth0.IPv4 with address 192.168.0.101.
Jul 3 14:58:05 pulseaudio[3683]: [pulseaudio] module-alsa-card.c: Failed to find a working profile.
Jul 3 14:58:05 pulseaudio[3683]: [pulseaudio] module.c: Failed to load module "module-alsa-card" (argument: "device_id="0" name="pci-0000_00_03.0" card_name="alsa_ca

and in messages:

Jul 3 14:58:04 shutdown[3929]: shutting down for system halt
Jul 3 14:58:05 kernel: [   90.616600] colord-sane[3886]: segfault at 18 ip 00007fa8dc5a2543 sp 00007fa8cb9808c0 error 6 in libc-2.13.so[7fa8dc529000+182000]

BTW there is also VirtualBox installed and following message is in the log
kernel: [ 38.497835] warning: VirtualBox uses 32-bit capabilities (legacy support in use) but I don't think thats really the issue…

So I'm looking for suggestions how to fix this. Should I update some driver or update BIOS or…? I'm really not an Linux power user so please be as specific as possible when additional information is needed or when you suggest some solution.

My system info:

Release 7.5 (wheezy) 64-bit
Kernel Linux 3.2.0-4-amd64
GNOME 3.4.2
Gallium 0.4 on llvmpipe (LLVM 0x209)
Experience: Fallback

ASUS UEFI BIOS Utility
Bios Version: 1005 x64 H87-PRO
Build date: 01/02/2014
ME Version: 9.0.2.1345
South Bridge Stepping: 05/C2
CPU: Intel Core i5-4670 @ 3.4GHz