I'm getting out of ideas. You did modprobe before running fdisk, didn't you?
Not a valid block device means that it can't open it. Could you post the output of lsmod to check that needed modules are loaded.