Have you tried the resample datamanagement tool?
http://resources.arcgis.com/en/help/main/10.1/index.html#//00170000009t000000
This is a recurring question for which I give you my recurring answer:
I had a similar problem and first tried to convert my data as well. But, than noticed my Geotiff had a compression applied ('PACKBITS'). After exporting my dataset (right click layer =>Export Data) to an uncompressed Tiff (Compression type: NONE), the problem was solved: NoData cells behave again like expected and you can carry out again common NoData operations. So have a look at your layer properties to see if your Tiff has been compressed as well and if so uncompress it.
Good luck and best wishes,
Alfred Wagtendonk