My Samsung phone's handbook recommends that any sd card to used in the phone is formatted on the phone because "..SD cards formatted on the PC may not work in the phone...". Therefore it is possible that cards formatted on the phone may not work in the PC. Why not try formatting the sd card on your PC, getting it working on your PC then try it in your phone.
Then try it the other way around i.e. format again on the phone then try it on your PC.