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:
http://www.forums.fedoraforum.org/sh...d.php?t=287248
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.