The only thing that stands out to me is the failure on lock_fsid and the error converting store message.
Here are the snip from OSD 19 of a full reboot starting with the shutdown complete entry, and going until all the reconnect messages.
2013-11-12 09:47:05.843425 7f7918e9d780 0 ceph version 0.72 (5832e2603c7db5d40b433d0953408993a9b7c217), process ceph-osd, pid 1734
2013-11-12 09:47:05.892704 7f7918e9d780 1 filestore(/var/lib/ceph/osd/ceph-19) mount detected xfs
2013-11-12 09:47:05.892718 7f7918e9d780 1 filestore(/var/lib/ceph/osd/ceph-19) disabling 'filestore replica fadvise' due to known issues with fadvise(DONTNEED) on xfs
2013-11-12 09:47:05.944312 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is supported and appears to work
2013-11-12 09:47:05.944327 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is disabled via 'filestore fiemap' config option
2013-11-12 09:47:05.944743 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: syncfs(2) syscall fully supported (by glibc and kernel)
2013-11-12 09:47:06.258005 7f7918e9d780 0 filestore(/var/lib/ceph/osd/ceph-19) mount: enabling WRITEAHEAD journal mode: checkpoint is not enabled
2013-11-12 09:47:07.567405 7f7918e9d780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 19: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:47:07.570098 7f7918e9d780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 19: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:47:07.570352 7f7918e9d780 1 journal close /var/lib/ceph/osd/ceph-19/journal
2013-11-12 09:47:07.571215 7f7918e9d780 1 filestore(/var/lib/ceph/osd/ceph-19) mount detected xfs
2013-11-12 09:47:07.572742 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is supported and appears to work
2013-11-12 09:47:07.572750 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is disabled via 'filestore fiemap' config option
2013-11-12 09:47:07.573234 7f7918e9d780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: syncfs(2) syscall fully supported (by glibc and kernel)
2013-11-12 09:47:07.574879 7f7918e9d780 0 filestore(/var/lib/ceph/osd/ceph-19) mount: enabling WRITEAHEAD journal mode: checkpoint is not enabled
2013-11-12 09:47:07.577043 7f7918e9d780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 23: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:47:07.578649 7f7918e9d780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 23: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:47:07.680531 7f7918e9d780 0 <cls> cls/hello/cls_hello.cc:271: loading cls_hello
2013-11-12 09:47:09.670813 7f8151b5f780 0 ceph version 0.72 (5832e2603c7db5d40b433d0953408993a9b7c217), process ceph-osd, pid 2769
2013-11-12 09:47:09.673789 7f8151b5f780 0 filestore(/var/lib/ceph/osd/ceph-19) lock_fsid failed to lock /var/lib/ceph/osd/ceph-19/fsid, is another ceph-osd still running? (11) Resource temporarily unavailable
2013-11-12 09:47:09.673804 7f8151b5f780 -1 filestore(/var/lib/ceph/osd/ceph-19) FileStore::mount: lock_fsid failed
2013-11-12 09:47:09.673919 7f8151b5f780 -1 ** ERROR: error converting store /var/lib/ceph/osd/ceph-19: (16) Device or resource busy
2013-11-12 09:56:37.556988 7f3793c21780 0 ceph version 0.72 (5832e2603c7db5d40b433d0953408993a9b7c217), process ceph-osd, pid 13723
2013-11-12 09:56:37.559314 7f3793c21780 1 filestore(/var/lib/ceph/osd/ceph-19) mount detected xfs
2013-11-12 09:56:37.559319 7f3793c21780 1 filestore(/var/lib/ceph/osd/ceph-19) disabling 'filestore replica fadvise' due to known issues with fadvise(DONTNEED) on xfs
2013-11-12 09:56:37.561350 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is supported and appears to work
2013-11-12 09:56:37.561360 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is disabled via 'filestore fiemap' config option
2013-11-12 09:56:37.562357 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: syncfs(2) syscall fully supported (by glibc and kernel)
2013-11-12 09:56:37.571030 7f3793c21780 0 filestore(/var/lib/ceph/osd/ceph-19) mount: enabling WRITEAHEAD journal mode: checkpoint is not enabled
2013-11-12 09:56:37.574273 7f3793c21780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 23: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:56:37.578189 7f3793c21780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 23: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:56:37.578854 7f3793c21780 1 journal close /var/lib/ceph/osd/ceph-19/journal
2013-11-12 09:56:37.579638 7f3793c21780 1 filestore(/var/lib/ceph/osd/ceph-19) mount detected xfs
2013-11-12 09:56:37.581110 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is supported and appears to work
2013-11-12 09:56:37.581118 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: FIEMAP ioctl is disabled via 'filestore fiemap' config option
2013-11-12 09:56:37.582014 7f3793c21780 0 genericfilestorebackend(/var/lib/ceph/osd/ceph-19) detect_features: syncfs(2) syscall fully supported (by glibc and kernel)
2013-11-12 09:56:37.583365 7f3793c21780 0 filestore(/var/lib/ceph/osd/ceph-19) mount: enabling WRITEAHEAD journal mode: checkpoint is not enabled
2013-11-12 09:56:37.585765 7f3793c21780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 24: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:56:37.588281 7f3793c21780 1 journal _open /var/lib/ceph/osd/ceph-19/journal fd 24: 10239344640 bytes, block size 4096 bytes, directio = 1, aio = 1
2013-11-12 09:56:37.589782 7f3793c21780 0 <cls> cls/hello/cls_hello.cc:271: loading cls_hello
After the 'restart ceph-osd-all' the admin sockets for all 4 OSDs on this host are present.
Let me know if there is additional logging or assistance I can provide to narrow it down.