The ndk comes with ndk-gdb, which supposedly allows you to debug native applications. Also, if you download the whole andriod open source project, they also have some version of gdb used for debugging. Look in the docs/ folder of the ndk to learn about using it. This tutorial might also prove helpful: http://vilimpoc.org/blog/2010/09/23/hello-gdbserver-a-debuggable-jni-example-for-android/
However, as shown in a recent question I asked: Running ndk-gdb with package not found error on motorola phone I still can't get it to work.
Edit: You said in the comments you were using a Samsung Device: Samsung decide to wreck havoc on some of the crucial internals required for native debugging, but it's easily fixable if you have root access to the device. If you use the --verbose flag, you'll probably find that the error is different than that, a package unknown error. That's because it's looking in /data/system/packages.list, but samsung renamed that file to /dbdata/system/packages.list. So if you make a symlink to that file in /data/system/packages.list, (requires root access) it should work. Or at least so claims the ndk mailing list: http://osdir.com/ml/android-ndk/2011-03/msg00036.html