Yes, it's possible because if the application was used by System and now that it's uninstalled, it creates a conflict. Since there is a system backup only accessible by system kernel, you can hard reset the phone again and the application will be restored, however, it's recommended to keep it next time you plan to remove apps from your phone. Install Titanium Backup in free mode and then you can use what applications can be removed based on their color: yellow and green is OK, red is not recommended.
