That's odd, I posted yesterday about what the issue was but there isn't a post, must have forgot to click the post button.
Anyway the problem is in your constant for Almost_Full_Depth:
Code:
CONSTANT Almost_Full_Depth : std_logic_vector(9 downto 0) := "0111110100";
which translates to 500, which means your code is still treating the FIFO as being 512 deep.
FYI, for the previous posters the FIFO was reconfigured to be 1024 just open the zip file of the FIFO IP directory and look at the xci file.