I thought I would comment because I think udev-rule debugging and particularly file permissions is something everyone should understand (particularly if you're writing the rules yourself).
You can watch udev add/remove devices by running "udevadm monitor" and then plug in the nxt; it'll look like this: http://sprunge.us/QLEJ
Then if you want to see what udev did with that event, you can do something like: http://sprunge.us/aPBi
which tells you pretty much everything you'd need to know. Of particular interest would be line 27: "read rules file: /etc/udev/rules.d/70-lego.rules"; so we know it is in fact reading the rules from 70-lego.rules.
It also tells you semi-interesting things like the path to the device node, in this case: /dev/bus/usb/003/003 (which the tutorial halfway mentions exists, but never tells you how to calculate it). The other less-intuitive way to come up with that path is by doing lsusb; it would tell you something like, in this case "Bus 003 Device 003: ID 0694:0002 Lego Group Mindstorms NXT"; and then you'd have to just know that Bus 003 Device 003 corresponds to /dev/bus/usb/003/003
So if we look at the permissions of /dev/bus/usb/003/003, http://sprunge.us/DaRZ
you'll see that in my case, the rules are obviously being applied. In that udevadm test, you can also see where the permissions came from on lines 60 and 61 of that second sprunge, "GROUP 1001 /etc/udev/rules.d/70-lego.rules:1" is particularly interesting to us.
Now, what I've seen frequently is where people follow ancient tutorials written by people who don't know what they are talking about, and/or run an ancient distribution with a dinosauric version of udev. You might see deprecated things like BUS=="usb" rather than SUBSYSTEM=="usb". There's another way to do ATTR iirc, one that's deprecated and still (halfway) works, and another completely broken way, but the way suggested in the tutorial is indeed the optimal way.
If I purposely broke my udev rules for example: http://sprunge.us/LMSS
you'll see on lines 44 and 45, that it bus is completely deprecated/removed in favor of subsystem, and therefore udev doesn't recognize it at all. We're also missing that nice "GROUP 1001 /etc/udev/rules.d/70-lego.rules:1" line as you can see, because udev can't magically fix broken rules, and therefore can't apply them at all.
If we then examined the permissions of /dev/bus/usb/003/004 (again, udevadm told us what the path to the device node is), http://sprunge.us/gPHD
you'll notice that the lego group no longer owns it.
If I tried nxjflash as my user now, I would be told the same thing you pasted earlier. Trying to fiddle with permissions manually is particularly painful: http://sprunge.us/diDR
But you could avoid all of that pain, if you just fixed your udev rules (no, running the nxjflash/nxjupload as root is most definitely not a valid solution). Also, the "lego" group, if you wanted to follow what the tutorial suggests, must firstly 1) exist in /etc/group and 2) your user must be a member of it in /etc/passwd and 3) the shell used to spawn nxjflash/upload must have been started after your user was added to the group, because the group membership of the parent process is inherited by its children. Re-logging in is the canonical way to accomplish this. You can also see group membership of your current shell by running "id".
I think calling the group "lego" originated from the lego usb tower used for infrared communications with the RCX; you would load the legousbtower module, and that would create a /dev/legousbtower0 device node, so it sort-of made sense to call the group allowed to use it "lego", to keeps things short. You could also call it something like "nxt-users" or something of that nature, but you'd need to update everything starting with your udev rules accordingly.
nxj toolchain developers: it might be worthwhile, instead of just saying "Ignoring device USB0::0x0694::0x0002::000000000000::RAW" to specify why it was ignored (no write permission in this case). Also, perhaps the tutorial should be expanded/updated with at least a subset of this information?
tl;dr: udev is your friend: use it.