Before and after you plug it in an USB port on linux
what does
say?
The results will let you know whether the kindle is detected and what it is detected as. For example, if it is jailbroken, it might be detected as an USB ethernet device, depending on whether USBnetworking was installed and what mode it is in.
wifi is unlikely to works because of security settings. The store won't work even if you get wifi working.