Ahh, your echo command running before the if is setting $? to 0, so the if is always true. Remove the echo and it should work. (edit: I see Arizona beat me to it)
BTW, You could simplify it a little, no need for the if/test on $?
Code:
ping -c 5 123.45.678.910 || shutdown -t 10 -r now