Just curious - how did you profile code running on the NDS? Emulator?
Emulators are generally pretty accurate at CPU timings, but other hardware timings are lacking, especially with the amount of time it takes the GPU to process certain operations. (DesMuMe is my usual emulator for quick testing, no$gba is the most hardware accurate and has an excellent debugger, but it still falls short of real hardware testing for timings.)
The NDS does have hardware timers, so I wrote a quick and dirty set of profiling functions. I can issue a start and stop keyed on a topic, and it will measure the number of cycles between the calls. So, any bit of the engine I wish to time, I just surround with matching start/stop calls using the same topic, and then print the results of all the topics out to a text console on the bottom screen. (If you're running the game, hit Select a few times to pull this up. Go withdraw a full squad of Pikmin and see the numbers change and the framerate drop.) It's crude but effective, and keeping in mind the 550k cycle limit per frame allows me to get a rough estimate of what percentage of my frame time is taken up by a particular routine.
I've generally found that my physics and AI calculations are proportionally slower on real hardware than the emulator reports, by a small margin. I suspect this is due to the ARM9's weird TCM cache implementation, but I really don't know what's going on. Graphics calculations are way different though, and are usually reported much faster by the emulators, so I always re-profile any graphics "optimizations" on real hardware to make sure I haven't run into something that the emulator just happens to run fast.
A huge downside with this technique is that color changes during H-blank (waiting period between scanlines) and more critically V-blank (rather long waiting period after each full screen draw) cannot be seen. When I was using this technique, I had the engine actually wait until all of V-blank had passed before it started doing the timing colors. This still ended up being pretty hard to read of course, as the colors would change flicker rapidly at 60FPS, couldn't be easily saved to view later, and were complicated significantly by the multi-pass nature of the engine, where each visible frame is actually composed of several hardware frames, all with totally different timings. So I scrapped that method almost immediately and wrote text-based profiling code that used the built in hardware timers.