At this point I'm unsure about the whole issue, re-read the whole thread:
- kernel-18.104.22.168.bfs is working as expected
- kernel-22.214.171.124.pae-bfs doesn't shutdown correctly
other users look live having some/similar shutdown issue using 126.96.36.199 kernel, but a custom 2.6.36.x works:http://www.pclinuxos.com/forum/index.php/topic,92384.0.html
this bug from fedora look to me very similar to your issue:https://bugzilla.redhat.com/show_bug.cgi?id=712060
all the above point the finger to some change in 188.8.131.52 kernel, while previous kernels (< 2.6.37.x) look like to not be affected.
Debugging this issue can be very difficult an time consuming, I would suggest to install kernel 184.108.40.206
until someone will find the underlying issue and possibly the solution.
(a note about the "loop" dependency you notice at shutdown: some service depends from other services, which in turn may depend
from the first, these messages only note about this "dependency loop" but are otherwise harmful, do not worry about that).