If your geodatabase has both feature classes and feature datasets, I believe you need to deal with each. That is, loop through the datasets and delete feature classes in the dataset and then empty datasets, and follow this by looping through remaining feature classes and deleting the empty ones.
import arcpy
arcpy.env.workspace = r'C:\Path\To\file.gdb'
for fds in arcpy.ListDatasets('','Feature'):
print "{}".format(fds)
features = 0
for fc in arcpy.ListFeatureClasses('','',fds):
count = int(arcpy.GetCount_management(fc).getOutput(0))
if count:
features += 1
print "\t{}: {} records".format(fc, count)
else:
print "\t{} records, deleting: {}".format(count, fc)
arcpy.Delete_management(fc)
print "{} has {} remaining features".format(fds, features)
if features == 0:
print "{} dataset is empty, deleting".format(fds)
arcpy.Delete_management(fds)
else:
print "{} has {} remaining features".format(fds, features)
for fc in arcpy.ListFeatureClasses():
count = int(arcpy.GetCount_management(fc).getOutput(0))
if count:
features += 1
print "\t{}: {} records".format(fc, count)
else:
print "\t{} records, deleting: {}".format(count, fc)
arcpy.Delete_management(fc)