After contacting Tech Support, I got this answer, which solved my problem.
After various testing it seems that there may be an issue with publishing an spk to ArcGIS Online if it was created in a version of CityEngine previous to 2016.1.
In order to determine if this is the case can you please complete the following test:
1. Upgrade your software to CityEngine 2016.1. This is the most current version and can be found in My Esri -> My Organizations -> Downloads
-- Make sure you uninstall any previous versions including 2016.0
2. Use your shapefile and rule file to recreate your spk again from scratch using 2016.1
3. Now try publishing to ArcGIS Online