After doing a couple hours of searching around for worms that looked like this, I stumbled across the a picture of a brittle star (Class Ophiuroidea), and realize the striking resemblance now. I guess it just hadn't come out far enough for me to see it's other legs, so I just assumed it to be a worm.
I'm pretty excited now with this find since it came with the rock.