In addition to going up several needle sizes, the most important thing is to bind off "in pattern" if you were doing ribbing before binding off you need to bind off in ribbing (and ribbing is stretchy!).
I like to think of binding off as this: it's just literally the action of pulling the one loop over the other. That's it. It is NOT necessarily (unless you are doing stockinette), knitting 2 and then pulling one over the other.
So to bind off in pattern you continue to do the type of stitch that you were doing, so for example if you you were doing a 1x1 rib you would knit 1, PURL 1 then pull the loop of the other, knit 1 pull over, purl 1 pull over etc.
If you just knitted all the way across as you bound off then you will have lost the stretchiness of the ribbing.