Sticking in the brighter LED's should be fine. An LED only sucks down what power is available to it, and even an ultrabright which normally takes more, if put on a lower power resistor, will only suck down as much power as it is given.
Remember, V = IR, so lets assume for a moment that your power supply is @ 5V, and your current LED's want 20mA. Assuming a 2.2V drop over the LED, we have 2.8V/20mA = 140ohms. So there are probably something on the order of a 150ohm resistors in series with your LED's to limit the current. Given that a higher power LED has a larger forward voltage drop, you probably need to snip out the current resistor and stick in a new one. Using the LED you suggested, you need a smaller resistor, something on the order of 70ohms.