I've noticed this probelm too, and thought it was introduced with the big June 6th update. My 3DS has powered on with one press of the power button since I got it. Then after the update, I started to worry when my 3DS wouldn't power on at all. It literally took about 6-8 seconds of holding the button for it to turn on. Strangely, there's normally a small boot-up time until I get to the main menu, but when I held the power button down it powered on directly to the main menu.
It's only happend a couple times since, and seems to occurr when I haven't played my 3DS for a length of time. Since I've been playing my 3DS constantly since Zelda came out, it hasn't happened again. I also thought that it could possibly be the button wearing out. I tend to press the power button on the right side of the button, and maybe it wasn't pressing it down correctly. Now I try to press the power button towards the left, or middle of the button.