Fortress, this may sound really basic but make sure you have the noseplug on facing the right way, with the rubberized flares facing away from you and the wire flush against the bridge of your nose. When I first started experimenting with the nose plug it was hurting me and I had trouble keeping it on my nose. I happened to see a synchro demonstration (at the 99 SCY nationals at Santa Clara) and saw the swimmer up close and realized I had been wearing the clip backwards - a real "a-ha" (or maybe "duh") moment for me.
Also try the different sizes to find the one that works for you. I like the Speedo clips because they are smaller. Also when its not on my nose I wear it on my left ring finger with the wire tucked underneath my wedding ring, I can swim fly or sprint free and not worry about losing it. Works great for meet warmups too.