It could be that Fedora cannot create a new partition despite there being free space available.
You can only have 4 primary partitions on a bios/mbr layout, and it is not unusual these days
for Windows and OEMs to use them all.
Check out post #4 in this thread:
I'm not familiar with Windows, but if you could post a screenshot of your current disk layout
that might enable someone to offer a solution.