I've contacted two larger YouTubers for collaboration (one with 90k subs and the other with 172k). The first one was done here on yttalk; I posted in a thread he had made. The main thing I said was: "We would love to have our channel featured on one of your tutorial videos." Since this is a thing he does, and as he liked our art, he asked for my email. I later suggested a full collaboration to him, and our collab video just went up on his channel yesterday.
The second person I emailed directly with a collaboration offer. She was open to the idea, and after we decided specifically on what to do, she added me on Skype to discuss the finer details. This video is still in the process of being created.
That is the state of things.