How are you sending out updates? It's possible that the problem is that the app ID is changing. To see if this is the case, modify the app to somehow report the value of chrome.runtime.id and have it sent back to you.
If this is the case, you can fix the ID by including a key property in your manifest.json. To get the value of the key property, install the app by dragging a CRX file to the Extensions page or from the Chrome Web Store and find the INSTALLED manifest.json file. (There is a doc on where to find it... don't recall the URL but you can Google for it.) Then copy the key property to your source manifest.json file.
UPDATE: Found the link. http://developer.chrome.com/apps/manifest/key.html