I have a Kingmax 1GB card and haven't had any problems using it with my original N-Gage. Being a larger card, it takes a bit longer to read when connecting/disconnecting from USB, but that's expected. As for performance the rest of the time, it works fine.
I recommend Kingmax cards for two reasons: 1) they're cheap, and 2) they come preformatted in a way that works with the N-Gage right out of the package. I've seen other N-Gage users recommend them in forums online, which is why I bought one. Works great.