Thanks again for your help Adam,
The problem was with my code. I was trying to add the new button before I had actually added CE to my web parts control.
Following code snippet soved the problem. Note how im adding the button after I add CE to the control (Just incase anyone makes the same mistake)...
// Add ce first
this.Controls.Add(_tb);
// Now add custom button into the editor
WebControl ctrl = this._tb.CreateCommandButton("MyButton", "video.jpg", "Insert Video");
ctrl.Attributes[
"onclick"] = "ShowMyDialog(this)";
this._tb.InsertToolControl(_tb.ToolControls.IndexOf("InsertDocument") + 1, "MyButton", ctrl);
Paul.