This question has been answered by Matthew Henderson in the Azure Mobile Services forum
The simplified version is you need to use one Live Connect app in the Developer Center (i.e. the same Client ID used by both the W8.1 & WP8 apps)
To do this you either need to either:
a) Start with the Windows 8.1 app which will register the SID with the Live Connect app (this is the documented and easiest path) and then re-use this Client ID in the Windows Phone 8 app
OR
b) If you already have a Windows Phone 8 app as I did then you can change the automatically created SID association in the Live Connect Developer Center to allow the Windows 8.1 app to use the existing Windows Phone 8 Client ID. This is a less well documented feature.