If you haven't already verified that your external/public IP address is changing, then I'd tend to assume that it isn't. Although there are exceptions (such as Om Nom Nom's ISP) where cable/DSL providers will assign a new/different IP address every time you connect, my experience has been that the public IP for any broadband connection will always receive the same IP address except in unusual circumstances (e.g., the ISP reconfigures their infrastructure) or after spending a long enough time disconnected that the address gets assigned to someone else.
The reason for this, even when you have a dynamic IP address, is that DHCP (the mechanism used to request a dynamic address) clients and servers both remember the last IP address each client has been assigned. When reconnecting, clients (such as your router) will typically request that they be given the same address again; servers will generally comply with this request if the address is available. If the client does not request a specific address and the server recognizes it, the server will frequently offer the same address again anyhow.
If you've confirmed that your external IP actually is changing, then I'm going to have to agree with Daisetsu: Assuming web-based chat, you're probably being blocked based on a cookie that the site has set.