Extra wires on dual switch install
Was it a single pole switch to begin with? Before running your own wire, there should have just been two wires tied to the switch (and a ground); the power coming in and the wire running out to the old light. The other wires should not be wired to the switch unless you want the switch to cut the items off as well (if they are downstream of it).

I drew up a quick, crude sketch of what you'll need to run this setup, regardless of what else is there. Get it down to the basics first and work up is the best way to troubleshoot.

Coming into your box should be the main hot line, I believe you said it was red. Pigtail off of it to the two commons on your new double switch and wire nut them all together. 

Next, take your old wire that ran to your light and connect it to one of the other screws. This is where you'd decide which switch to control which item.

Take your new wire that you ran from your fan and connect it to the last screw. Then back at your fan/light, wire one of the lights to the fan and one to the light. Twist together and cap off the neutrals and you should have a working system.

I'm not certain of what those other wires are there for based on your description.. were they connected to the old switch? But, this will get the fan and light working.

Also, like mentioned in Iggy's answer, this won't allow you to control the fan speed from the switch, it'll just cut it on and off.