[Samsung Galaxy Nexus] jup007:
This is after fdocomo v3, right? So your files get rebuild from what's in the factory and you still get what, unknown IMEI? This may also be that files in factory are simply broken and were broken before backup. They contain IMEI, so if something happened to them, this would show as such problem. However, if /factory is lost, I don't know how to fix it. There are things worth trying though - you may try restoring nv_data files from nv_core files, which is actually pretty simple if you have busybox. With rw mounted factory and airplane mode on, do:

shell@android:/factory # cd /factory
shell@android:/factory # rm nv_data.bin*
shell@android:/factory # rm .nv_data.bak*
shell@android:/factory # rm /data/radio/nv_data.bin.*
shell@android:/factory # ls -la
-rwx------ radio radio 1048576 2012-04-20 03:13 .nv_core.bak
-rwx------ radio radio 32 2012-04-20 03:13 .nv_core.bak.md5
-rwx------ radio radio 1 2012-04-20 03:13 .nv_state
drwxr-xr-x radio radio 2011-01-03 15:26 bluetooth
-rw------- radio radio 640 2011-01-03 15:26 hdcp.keys
drwxrwxr-x radio radio 1999-12-31 16:02 imei
drwx------ root root 1969-12-31 16:00 lost+found
-rw------- radio radio 4674 2012-04-20 03:13 nv.log
drwxrwx--- system radio 1999-12-31 16:00 wifi
-rw-r--r-- radio radio 144 2011-01-03 15:26 wv.keys
# busybox killall rild

wait lets say 30 secs

shell@android:/factory # ls -la
-rwx------ radio radio 1048576 2012-04-20 03:13 .nv_core.bak
-rwx------ radio radio 32 2012-04-20 03:13 .nv_core.bak.md5
-rwx------ radio radio 2097152 2012-05-10 00:34 .nv_data.bak
-rwx------ radio radio 32 2012-05-10 00:34 .nv_data.bak.md5
-rwx------ radio radio 1 2012-04-20 03:13 .nv_state
drwxr-xr-x radio radio 2011-01-03 15:26 bluetooth
-rw------- radio radio 640 2011-01-03 15:26 hdcp.keys
drwxrwxr-x radio radio 1999-12-31 16:02 imei
drwx------ root root 1969-12-31 16:00 lost+found
-rw------- radio radio 4847 2012-05-10 00:34 nv.log
-rwx------ radio radio 2097152 2012-05-10 00:34 nv_data.bin
-rwx------ radio radio 32 2012-05-10 00:34 nv_data.bin.md5
drwxrwx--- system radio 1999-12-31 16:00 wifi
-rw-r--r-- radio radio 144 2011-01-03 15:26 wv.keys
shell@android:/factory # cat nv.log
(...)
Thu May 10 00:34:19 2012: NV backup has been rebuilt.
Thu May 10 00:34:19 2012: backup NV restored from Secondary bak.
Thu May 10 00:34:23 2012: MD5 open fail. (No MD5 file) : /data/radio/nv_data.bin.md5
Thu May 10 00:34:23 2012: NV restored.(GED)

What this does is gives rild (radio interface Samsung daemon) chance to rebuid /factory from .nv_core backup. It knows how to do it, but normally can't do it on startup, since /factory is ro mounted. By mounting it rw, deleting files that are broken and killing daemon (which is service, so it gets restarted by android magicaly almost immediatelly), it gets chance. So try this. If you don't have busybox, just do ps, find rild there and PID number and do kill <PID>.

If this doesn't help, your secondary backup .nv_core.bak is also broken or it's really HW issue. In either case, this would require special tools to fix. But this is worth trying as last resort. I did it on my phone just to test this theory again.

EDIT: And I don't believe it's HW issue. If it was, generic IMEI wouldn't work. But it does for you and generic IMEI is nothing else then nv_data.bin that is hardcoded somewhere in the system to be used if factory doesn't exist. But if your /factory is broken and you don't have backup, you'd still need SPTBox or something similar to generate new files from scratch. So send it to somebody or find some Samsung repair place...